Yong's Tech Story

https://school.programmers.co.kr/learn/courses/30/lessons/42885

문제 풀이 (JAVA)

import java.util.*;
class Solution {
    public int solution(int[] people, int limit) {
        int answer = 0;
        int len = people.length;
        Arrays.sort(people); // 오름차순 정렬
        int lt=0,rt=len-1; // 왼쪽 포인터 = 최소값, 오른쪽 포인터 = 최대값
        int sum=0;
        while(lt <= rt){
            // sum > limit라면 lt==rt가 될수있고, sum<=limit라면 lt>rt의 경우가 생기므로 조건설정
            sum = people[lt] + people[rt];
            if(sum > limit){ // 무게제한을 초과한다면
                answer++;
                rt--; // 오른쪽 포인터만 증가
            }
            if(sum <= limit){ // 무게제한을 맞췄다면
                lt++; // 왼쪽 포인터 증가 = 다음 최소값
                rt--; // 오른쪽 포인터 감소 = 다음 최대값
                answer++;
            }
        }
        return answer;
    }
}

주요 핵심 포인트

1. 최소한의 구명보트 수를 구하려면 최대몸무게를 가진사람 + 최소몸무게를 가진사람이 같이 타야 한다.

2. 배열을 오름차순 정렬하여 무게를 최소~최대로 정렬하였다.

3. 왼쪽 포인터는 최소 몸무게를 가진 사람 , 오른쪽 포인터는 최대 몸무게를 가진사람으로 두 사람의 몸무게 합이 초과한다면 최대 몸무게를 가진사람은 혼자 타야 하고, 다음 최대 몸무게를 가진사람과 비교하여야 한다.

4. while문이 계속 반복한 결과 lt와 rt가 만나는 지점에서 rt만 감소하는 경우 lt==rt가 되고, lt는 증가하고, rt는 감소하는 경우 lt > rt 가 되므로 while문 조건을 lt <= rt로 설정해주었다.

5. while문이 종료했을시 최적의 구명보트 숫자를 리턴한다.

개선해야할 사항

: 위 문제를 이해하고 투포인터를 적용하는데에는 1시간 이상 걸렸다. 투 포인터의 문제 중 기본적인 문제이므로 문제의 접근 방식을 좀 더 빠르게 발견하는 연습을 해야겠다.

문제 풀이 (JAVA)

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;

public class part7_12 {

	static int[][] graph;
	static int[] visit;
	static int N;
	static int cnt;

	public static void main(String[] args) throws IOException {
		// 경로탐색(DFS)
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

		StringTokenizer token = new StringTokenizer(br.readLine());
		N = Integer.parseInt(token.nextToken());
		int M = Integer.parseInt(token.nextToken());

		String[] str = new String[M];

		for (int i = 0; i < M; i++) {
			str[i] = br.readLine();
		}
		bw.write(Integer.toString(solution(str, N)));
		bw.flush();
		bw.close();
	}

	private static int solution(String[] array, int N) {
		graph = new int[N + 1][N + 1];
		visit = new int[N + 1];
		for (int i = 0; i < array.length; i++) {
			String[] str = array[i].split(" ");
			int a = Integer.parseInt(str[0]);
			int b = Integer.parseInt(str[1]);
			graph[a][b] = 1;
		}
		visit[1] = 1;
		dfs(1);
		return cnt;
	}

	private static void dfs(int n) {
		if (n == N) {
			cnt++;
		} else {
			for (int i = 1; i < graph.length; i++) {
				if (graph[n][i] == 1 && visit[i] == 0) {
					visit[i] = 1;
					dfs(i);
					visit[i] = 0;
				}
			}

		}
	}
}

주요 핵심 포인트

1. String으로 들어오는 경로 (x1, x2) 를 graph[x1][x2]에 저장한다.

2. 모든 경로를 graph에 저장하였을시 연결점을 행과 열로 구분하여 볼 수 있다.

3. 이미 방문한 경로는 다시 방문할수 없으므로, 방문하였을시 visit[n]을 1, 방문을 종료하였을시 0으로 변경함으로써 동일한 숫자 경로를 0으로 변경한다.

4. if문에서 방문하지 visit[n] == 0 조건을 걸어줌으로써 방문하지 않은 숫자에 대해서만 탐색하도록 하는 알고리즘이다.

5. 방문을 종료하고 나서는 해당 숫자를 다시 한번 방문 하는 케이스를 고려하기 위하여 vsit[n] = 0 으로 초기화한다.

6. 구하고자 하는 N, 즉  dfs(N)이 도달하였을때에 카운트를 증가하였다.

개선해야할 사항

1.  해당 문제를 풀려고 하였으나 중간에 막혀 다른 강의 소스를 참조하게 되었다. 스택으로 풀고자 하였으나, 스택 프레임을 제대로 구현하지 못하여 정상적인 데이터를 출력하지 못하였다. 모든 케이스를 탐색하기 위하여 해당 케이스를 방문하였는지, 방문하지 않았는지를 생각하고 트리를 그려 확인하는 연습이 필요할듯 하다. dfs는 많은 연습이 필요한 알고리즘이다.

문제 풀이 (JAVA)

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class part7_8 {
	static int K; // 송아지 위치
	static int level; // 레벨(점프횟수)

	public static void main(String[] args) {
		// 송아지 찾기1(BFS)
		Scanner input = new Scanner(System.in);

		int N = input.nextInt(); // 철수의 위치
		K = input.nextInt(); // 송아지의 위치
		bfs(N);
	}

	private static void bfs(int N) {
		Queue<Integer> queue = new LinkedList<>();
		int min = Integer.MAX_VALUE; // 최소 거리 변수
		queue.offer(N); // 철수의 위치 N 삽입
		while (queue.peek() != K) { // 철수의 위치가 송아지의 위치가 아닐동안 반복
			int cur = queue.peek(); // 철수의 현재 위치 변수
			min = Integer.MAX_VALUE; // 최소 거리 변수 초기화
			queue.offer(cur + 1); // 점프 +1
			queue.offer(cur - 1); // 점프 -1
			queue.offer(cur + 5); // 점프 +5
			int len = queue.size(); // 큐의 경우 사이즈
			for (int i = 0; i < len; i++) {
				int num = Math.abs(K - queue.peek()); // 최소거리 변수(송아지의 위치-철수의 점프 후 위치)
				if (min > num) { // 최소 거리를 저장
					min = num;
				}
				queue.offer(queue.poll()); // 큐의 변수를 한바퀴 돌린다.
			}
			for (int i = 0; i < len; i++) {
				// 지정한 최소거리가 아니라면 큐에서 제거
				if (min != Math.abs(K - queue.peek())) {
					queue.poll();
				} else {
					// 지정한 최소거리라면 큐에 다시 넣는다.
					queue.offer(queue.poll());
				}
			}
			// 한번 다 돌았을시 점프후 최소거리 변수만 큐에 남음.
			level++; // 횟수 카운트 증가
		}
		System.out.print(level);
	}
}

주요 핵심 포인트

1.  점프 한번시 +1, -1 , +5 만큼 갈 수 있으므로 경우의수는 3가지가 된다. 그 중 목표값 K와 가장 가까운 값을 K- (이동한값) 중 가장 크기가 적은 값이 송아지의 위치와 가까워지므로 최소값을 Math.abs()로  구하였다.

2. 철수의 첫번째 값 N을 큐에 넣고, +1,-1,+5의 증가되는 값들을 뒤이어 차례로 넣는다.

ex) 철수의 처음 위치 = 5 라면 큐 (5 <- 6 <- 4 <- 10) , 송아지의 위치 = 14

3. 송아지의 위치와 큐에 적재되어 있는 값들 중 (송아지의 위치- 적재된 큐) 를 하여 가장 차이가 적은 값이 최적의 이동값으로 큐를 앞부터 비교하여 한번씩 재적재하여 최소값을 구한다.

ex) 14 - 5 = 9 , 14 - 6 = 8 , 14 - 4 =10 , 14 - 10 = 4   => 최소값 = 4

4.  재적재된 큐와 최소값이 일치하는지 다시 비교하여 일치하지 않는 경우 제거하고, 일치하는 경우 큐에 재적재하였다.

ex) 큐( 5 <- 6 <- 4 <-10) -> (6 <- 4 <- 10) -> (4<- 10) -> (10)

5. 최종적으로 하나의 값이 남으며 해당 값이 다음 점프 값이 되며, 점프횟수를 가리키는 level을 1 증가시킨다.

6. 1~5를 반복하여 점프한 최종 값이 송아지의 위치와 같아진다면 반복을 종료한다.

개선해야할 사항

1.  위처럼 생각하여 풀이하였을 때, 시간 효율성은 괜찮게 나왔다. 강의와 비교하였을때 강의에서의 시간 효율성보다 내가 풀었던 시간 효율성이 조금 더 괜찮지 않나 싶다. K의 값이 크더라도 5씩 증가하기 때문에 K/5 * 2n번을 반복하므로 모든 수를 비교하지는 않아 시간 효율성이 좋게 나온듯 하다. bfs는 최적의 경로 문제를 풀기에 적절한 문제임을 인지하자.

https://school.programmers.co.kr/learn/courses/30/lessons/60057

문제 풀이 (JAVA)

import java.util.*;
class Solution {
    public int solution(String s) {
        int answer = Integer.MAX_VALUE; // 최대 숫자 길이 임의로 설정
        List<String> slist = new ArrayList<>(); // substring 문자열 저장 리스트
        String str=""; // 글자 개수별로 나눈 문자를 저장할 변수
        String nstr=""; // 새로 조립될 문자를 저장할 변수
        int cnt = 1; // 문자의 개수를 세는 카운트 변수
        if(s.length() == 1){ // 테스트케이스 5번 예외처리
            return 1; // 글자가 1개일때에는 조건문을 돌지 않는다.
        }
        for(int i=1; i<s.length(); i++){ // 자를 글자 수 = i
            for(int j=0; j<s.length(); j+=i){  // j는 글자수 +i 만큼 증가
                if(j+i < s.length()){ // 글자열이 최대 문자길이를 안넘긴다면
                    str = s.substring(j,j+i); // 글자수 i 만큼 잘라서 저장
                }else{ // 자를 글자열이 최대 문자길이를 넘어간다면
                    str = s.substring(j,s.length()); // 남은 마지막 문자까지 저장
                }
                slist.add(str); // 리스트에 자른 글자열 저장
            }
            for(int k=0; k<slist.size()-1; k++){ // k+1과 비교하므로 size()-1 까지 비교
                // 리스트에 저장한 단어 문자열 i번째와 i+1번째가 같다면
                if(slist.get(k).equals(slist.get(k+1))){ 
                    cnt++; // 카운트 증가 (초기 카운트=1, 따라서 2이상)
                }else{ // 다음 문자열 리스트와 같지 않다면
                    if(cnt > 1){ // 같은 문자열 카운트가 2 이상이라면
                        nstr += cnt + slist.get(k); // 숫자 + 문자열 저장
                    }else{ // 같은 문자열 카운트가 1, 즉 없다면
                        nstr += slist.get(k); // k-1에서 초기화한 글자 출력
                    }            
                    cnt=1; // 다음 문자열 k+1의 카운트 초기화
                }
                // 마지막 size-2 인덱스 처리(마지막 문자열 출력)
                if((k+1) == slist.size()-1){
                    if(cnt > 1){
                        nstr += cnt + slist.get(k+1);
                    }else{
                        nstr += slist.get(k+1);
                    }                     
                }
            }
            // 기존에 저장한 문자열의 길이보다 작다면 결과값 변경
            if(answer > nstr.length()){
                answer = nstr.length();
            }
            slist.clear(); // 리스트 초기화
            nstr=""; // 문자열 초기화
            cnt=1; // 카운트 변수 초기화
        }
        return answer;
    }
}

주요 핵심 포인트

1. for문의 i는 자를 문자열의 길이를 차례로 증가시키기 위하여 사용하였다.

2. for문의 j+=i 를 선언함으로써 다음 문자열의 길이를 반복하여 자른다. j+i가 문자열의 길이를 초과하는지 여부를 판단하여 문자열을 잘랐다.

3. 자른 문자열을 리스트에 저장하여, k번째와 k+1 번째가 같다면 cnt는 1씩 증가하였고, 초기 cnt는 1로 설정하였다. 따라서 k번째와 k+1번째가 달라질 경우 cnt의 크기에 따라 2이상이면 숫자와 함께 출력, 1이면 단일 문자열로 그대로 출력하였다. 마지막에 cnt=1 로 설정 한것은 다음 문자열의 개수를 미리 설정한 것이다. 비교문은 버블 정렬과 비슷한 알고리즘이다.

4. 마지막 인덱스에 도달했을때 경우를 출력하기 위하여  마지막에 조건절을 추가하였다.

5. 새로운 nstr 문자열 길이가 기존 answer보다 작다면 answer을 변경하였다.

6. 다음 문자열을 저장하기 위하여 clear()를 사용하여 리스트를 초기화하였고, nstr , cnt 또한 초기화하였다.

개선해야할 사항

: 해당 문제를 깔끔하게 풀었다고는 할 수 없을 것 같다. 문자열의 길이가 1~1000이하였기에 중첩되는 for문에서 시간초과 오류가 나지 않았다. 문자열의 길이가 매우 크다면, 해당 로직은 분명히 시간 초과 오류를 겪을 것이다. for문을 최소화 할수 있는 방법이 있는지 탐색해보아야겠다.