GOSE_KOSE

안녕하세요. 회사와 함께 성장하고 싶은 KOSE입니다.

이번 포스팅은 프로그래머스 표현 가능한 이진트리 자바 풀이를 작성하고자 합니다.

문제 출처: https://school.programmers.co.kr/learn/courses/30/lessons/150367

1. 풀이 소스

class Solution {
    
    int possible;
    
    public int[] solution(long[] numbers) {
        int[] answer = new int[numbers.length];
        
        for (int k = 0; k < answer.length; k++) {
            String binaryNum = Long.toBinaryString(numbers[k]); // 숫자를 바이너리 이진 문자열로 변경 toBinaryString()
            
            int fullTreeLen = 0;
            int h = 1; // 포화 이진트리를 만들기 위한 높이
            
            while (fullTreeLen < binaryNum.length()) {
                fullTreeLen = (int) Math.pow(2, h++) - 1;
            }
            
            boolean[] isOne = new boolean[fullTreeLen]; // 포화 이진 트리를 생성하기 위한 배열
            
            // 참조#1
            int notDummyIdx = isOne.length - binaryNum.length(); // 더미 문자열이 아닌 인덱스
            for (int i = 0; i < binaryNum.length(); i++) {
                isOne[notDummyIdx++] = binaryNum.charAt(i) == '1'; // 더미 문자열이 아닌 인덱스부터 대응되는 인덱스의 문자열이 1인지 판단 
            }
            
            possible = 1; // 정답 초기화
            dfs(0, isOne.length - 1, false, isOne); 
            answer[k] = possible;
            
        }
        return answer;
    }
    
    void dfs(int start, int end, boolean isParentZero, boolean[] isOne) {
        if (possible == 0) return;
        
        int mid = (start + end) / 2; // 포화 이진 트리에서 부모 노드는 자식 노드의 위치의 중간

        if(isParentZero && isOne[mid]) { // 만약 부모가 zero인데, 해당 자식 노드가 1이라면 유효성 X
            possible = 0;
            return; // 종료
        }

        if(start != end) { // 참조#2
            dfs(start, mid - 1, !isOne[mid], isOne); // !fullTree[mid] -> 만약 1이었다면 true 이므로 false
            dfs(mid + 1, end, !isOne[mid], isOne); // 만약 0이었다면 false -> true 즉 부모가 0이므로 자식 노트가 1이 된다면 유효성 X
        }

    }
}

// 문제 해결 방안
// 1. 이진 스트링으로 만들기
// 2. 포화 이진트리로 만들기
// 3. 각 노드가 부모노드가 된다고 가정할 때, 부모노드가 0이라면 자식 노드 1을 가질 수 없으므로 유효성 판단

2. 풀이 중점 사항

문제 풀이 순서는 다음과 같습니다.

-  이진 스트링으로 만들기

-  포화 이진트리로 만들기

-  포화 이진트리로 생성하는 과정에서 이진 문자열을  다시 숫자로 변경한다고 생각할 때, 값이 변경되지 않는 선에서 앞에 0을 여러 개 추가할 수 있습니다. (포화 이진트리 개수 내로)

-  각 노드가 부모노드가 된다고 가정할 때, 부모 노드가 0이라면 자식 노드 1을 가질 수 없으므로 유효성을 판단하기

이진 스트링으로 변경하기

 String binaryNum = Long.toBinaryString(numbers[k]); // 숫자를 바이너리 이진 문자열로 변경 toBinaryString()

포화 이진트리로 만들기

int fullTreeLen = 0;
int h = 1; // 포화 이진트리를 만들기 위한 높이

while (fullTreeLen < binaryNum.length()) {
    fullTreeLen = (int) Math.pow(2, h++) - 1;
}

포화 이진트리는 노드의 개수가 2^h - 1입니다. 따라서, 이진 스트링으로 설정된 문자열의 개수가 포화 이진트리에 해당할 때까지, 반목문으로 fullTreeLen의 개수를 설정합니다.

참조 #1

// 참조#1
int notDummyIdx = isOne.length - binaryNum.length(); // 더미 문자열이 아닌 인덱스
for (int i = 0; i < binaryNum.length(); i++) {
    isOne[notDummyIdx++] = binaryNum.charAt(i) == '1'; // 더미 문자열이 아닌 인덱스부터 대응되는 인덱스의 문자열이 1인지 판단 
}

만약 문자열이 101010 (42) 이라고 가정하겠습니다.

해당 문자열의 값을 바꾸지 않는 선에서 포화 이진트리를 만들려면 0101010 이렇게 만들 수 있습니다.

//           1
//        1      1
//      0   0  0   0

여기서 더미 문자열이 아닌 인덱스 notDummyIdx란 실제 이진 문자열에서 유효한 0, 1이 아닌, 앞에 추가될 0의 개수를 의미합니다. isOne 배열은 포화 이진트리 개수로 선언된 boolean 배열이므로 만약 이진 스트링의 특정 위치의 값이 1이 아닌 경우 모두 false로 설정합니다.

참조 #2

앞 서 1 : true, 0 : false로 설정한 이유는 다음과 같습니다.

값을 변경하지 않는 선에서 포화 이진 트리를 구성하기 위해서는 부모 노드가 1인 경우 자식 노드를 0으로 추가하여 만들 수 있습니다. 하지만 부모 노드가 0 임에도 자식 노드가 1인 값이 존재한다면, 이는 유효한 경우가 아닙니다.

// 95

// 1011111
//             1
//           0    1
//         1  1  1  1 

// 42
// 010101
//           1
//         1   1
//        0 0 0 0

예를 들어, 1(노드)을 연결하여 이진 트리를 생성한 후, 빈 공간에 0을 삽입하여 포화 이진트리를 생성해야 하는데,
부모노드가 0이고 자식 노드가 1이라면, 이는 하나로 연결된 트리를 만들 수 없습니다.

따라서, 부모 노드가 0인 경우에 자식 노드가 1인 경우를 찾아서 하나라도 있다면 0을 리턴하면 됩니다.

그 외에는 모두 더미 노드로 0을 채워 넣을 수 있으므로 포화 이진트리로 요구하는 숫자를 완성시킬 수 있습니다.

    void dfs(int start, int end, boolean isParentZero, boolean[] isOne) {
        if (possible == 0) return;
        
        int mid = (start + end) / 2; // 포화 이진 트리에서 부모 노드는 자식 노드의 위치의 중간

        if(isParentZero && isOne[mid]) { // 만약 부모가 zero인데, 해당 자식 노드가 1이라면 유효성 X
            possible = 0;
            return; // 종료
        }

        if(start != end) { // 참조#2
            dfs(start, mid - 1, !isOne[mid], isOne); // !fullTree[mid] -> 만약 1이었다면 true 이므로 false
            dfs(mid + 1, end, !isOne[mid], isOne); // 만약 0이었다면 false -> true 즉 부모가 0이므로 자식 노트가 1이 된다면 유효성 X
        }

    }

부모 노드를 찾기 위해 자식 노드들의 위치의 중간 인덱스를 찾은 후, start, end가 다르다면 (계속 좁혀가기 때문에 결국 하나로 수렴하게 됨) 부모 노드의 자식 노드를 탐색하여 1 여부를 판단합니다.

!isOne [mid]는 만약 mid 인덱스에 속해있는 값이 1이라면 isOne[mid]는 true입니다.

다음 노드들은 0 혹은 1이어도 상관없으므로 false를 리턴하여 
if (isParentZero && isOne[mid]에 걸리지 않습니다.

반면, 0이라면, isOne[mid]는 false가 되고, !isOne[mid]가 true가 되므로,
parent가 0이면서, 자식 노드의 값이 1이라면 possible = 0이 되어 리턴됩니다.

이상으로 표현 가능 이진트리에 대한 설명을 마치도록 하겠습니다.

감사합니다!

안녕하세요. 회사와 함께 성장하고 싶은 KOSE입니다.

이번 포스팅은 프로그래머스 합승 택시 요금 자바 풀이를 작성하고자 합니다.

문제 출처: https://school.programmers.co.kr/learn/courses/30/lessons/72413

1. 풀이 소스

import java.util.*;

class Solution {
    
    static final int MAX = Integer.MAX_VALUE;
    List<List<Edge>> graph = new ArrayList<>();
    
    // 다익스트라
    // 각 노드간 연결관계 및 가중치 설정
    // 각 간선의 가중치 최대로 초기화
    // 우선순위 큐로 간선의 최단거리로 업데이트 
    public int solution(int n, int s, int a, int b, int[][] fares) {        
        for (int i = 0; i <= n; i++) graph.add(new ArrayList<>()); // 이차원 리스트 생성
        
        for (int[] fare : fares) {
            graph.get(fare[0]).add(new Edge(fare[1], fare[2])); // 양방향 간선 설정
            graph.get(fare[1]).add(new Edge(fare[0], fare[2]));
        }
        
        int[] costS = new int[n + 1]; // 다익스트라 배열 초기화        
        int[] costA = new int[n + 1];
        int[] costB = new int[n + 1];
        
        Arrays.fill(costS, MAX); // 다익스트라 알고리즘을 적용하기 위해 값 MAX_VALUE 설정
        Arrays.fill(costA, MAX);
        Arrays.fill(costB, MAX); 
        
        costS = dijkstra(s, costS); // 시작점(s)을 기준으로 각 노드별 최단 거리 구하기 참조#1
        costA = dijkstra(a, costA); // 시작점(a)를 기준으로 각 노드별 최단 거리 구하기 
        costB = dijkstra(b, costB); // 시작점(b)를 기준으로 각 노드별 최단 거리 구하기
        
        int answer = MAX;
        for (int i = 1; i <= n; i++) answer = Math.min(answer, costS[i] + costA[i] + costB[i]);  // 참조#2 
        
        return answer;
    }
    
    int[] dijkstra(int start, int[] costs) {
        PriorityQueue<Edge> queue = new PriorityQueue<>(Comparator.comparing((Edge e) -> e.cost));
        
        queue.add(new Edge(start, 0)); // 시작점에서 시작점으로 출발하는 노드이므로 0으로 초기화
        costs[start] = 0; // 시작점의 비용은 0
        
        while(!queue.isEmpty()) {
            Edge now = queue.poll(); // 우선순위 큐에 의해 간선이 적은 순서대로 queue에서 poll
            
            if (now.cost > costs[now.e]) continue; // 만약 x 노드로 가려는 가중치(비용)이 x로 가는 최단거리 배열의 값보다 크다면 패스
            
            for (Edge next : graph.get(now.e)) { // 그래프에 있는 e에서 출발하는 간선을 꺼내 간선이 이동하는 위치에 대한 거리가 최단 거리 값보다 작으면 업데이트
                int cost = next.cost + costs[now.e]; // 다음 노드로 가는 간선의 비용 + 현재 노드로 오는데 걸린 최단거리 비용 => 다음 노드에 대한 최종 비용 
                
                if (costs[next.e] > cost) { // 위에서 계산한 cost가 더 작다면
                    costs[next.e] = cost;
                    queue.add(next); // 현재 계산한 간선은 유효성이 있으므로 (더 작은 비용으로 다음 노드로 움직일 수 있으므로) queue에 입력
                }
            }
        }   
        return costs;
    }    
}

class Edge {
    
    int e; // 노드 번호
    int cost; // 비용
    
    Edge(int e, int cost) {
        this.e = e;
        this.cost = cost;
    }
}

2. 풀이 과정

참조#1

다익스트라 알고리즘은 특정한 정점에서 다른 정점으로 가는 최단거리를 계산할 수 있습니다. S지점은 합승하여 이동하는 구간으로 S를 시작점으로 가는 정점들은 모두 합승하였을 때, 드는 비용입니다.

A를 시작점으로 가는 정점들은 A(도착점)을 기준올 A가 혼자 택시를 타고 이동할 때 드는 비용입니다.

즉 합승은 시작점을 S,

A, B가 도착해야 하는 도착지점을 시작점으로 계산하여 다익스트라 알고리즘을 적용하는 것입니다.

이렇게 계산하게 된다면, 참조#2를 이용할 수 있습니다.

참조#2

(해당 그림은 양방향 간선으로 표현해야 하지만, 이해를 돕기 위해 출발 지점에서 어디로 움직인다는 화살표를 추가하였습니다)

각 택시요금의 합은 S -> 합승 끝 비용 + A -> S 비용 + B -> S의 비용으로 구할 수 있습니다.

즉, 합승이 끝나는 지점과 A, B가 끝나는 지점까지 드는 비용의 합이 최소가 되는 지점을 구한다면 가장 비용을 절감하는 위치를 구할 수 있는 것입니다. 

따라서, 어느 지점 (인덱스)에 도착했을 때, 세 비용의 합이 가장 적은 위치를 구하면 되는 것입니다.

for (int i = 1; i <= n; i++) answer = Math.min(answer, costS[i] + costA[i] + costB[i]);  // 참조#2

이상으로 합승 택시 요금 구하기 문제 풀이를 마치도록 하겠습니다. 감사합니다.!

안녕하세요. 회사와 함께 성장하고 싶은 KOSE입니다.

이번 포스팅은 프로그래머스 - 숫자 카드 나누기 문제 해결에 대한 글을 작성하도록 하겠습니다.

문제 소스: https://school.programmers.co.kr/learn/courses/30/lessons/135807

1. 풀이 소스

//14:49 

class Solution {
    public int solution(int[] arrayA, int[] arrayB) {
        // 나눌 수 있다 = 정수로 약분 가능 = A는 gcdA의 배수이다 
        
        int gcdA = findGCD(arrayA); // A 최대 공약수 찾기
        int gcdB = findGCD(arrayB);
        
        if (gcdA == gcdB) return 0; // 만약 두 최대 공약수가 같다면 어떻게든 두 배열에서 하나 원소 이상씩은 나눠짐
        
        boolean isGCDA = isGCD(gcdA, arrayB); // A배열의 최대 공약수로 B 배열을 나눌 수 있는지 판단
        boolean isGCDB = isGCD(gcdB, arrayA);
        
        if (!isGCDA && !isGCDB) return gcdA <= gcdB ? gcdB : gcdA; // 둘 다 가능한 경우 (false) 더 큰 수
        else if (!isGCDA) return gcdA; // 만약 gcdA만 arrayB의 원소를 나눌 수 없는 경우
        else if (!isGCDB) return gcdB;
       
        return 0;
    }
    
    
    int findGCD(int[] arr) { // 배열에서 공통된 최대 공약수 찾기
        int gcd = arr[0]; // 첫번째 원소
        
        for (int num : arr) {
            gcd = getGCD(gcd, num);
        }
        
        return gcd;
    }
    
    int getGCD(int x, int y) { // 유클리드 호제법으로 최대 공약수 찾기
        if (y == 0) return x;        
        return getGCD(y, x % y);
    }
    
    boolean isGCD(int gcd, int[] arr) { // 찾은 최대 공약수가 배열에서 나뉘어 지는지
        for (int num : arr) {
            if (num % gcd == 0) return true; 
        }
        
        return false;
    }

}

2. 풀이 과정

해당 문제는 최대 공약수를 찾는 과정이 key였습니다. 최대 공약수는 재귀로 해결할 수 있습니다.

int getGCD(int x, int y) {
    if (y == 0) return x;
    else getGCD(y, x % y);
}

만약 getGCD(4, 2)를 입력할 경우 시뮬에이션은 다음과 같습니다.

getGCD(4, 2)

= getGCD(2, 4 % 2)

= getGCD(2, 0)

y == 0 : return x => 2

따라서, return 2

이러한 방식으로 배열 원소에 대한 공통의 최대 공약수를 찾은 후, gcdA는 arrayB, gcdB는 arrayA에 적용하여 나눌 수 있는지 파악하는 것이 중요하였습니다.

이상으로 프로그래머스 숫자 카드 나누기 자바 문제를 마치도록 하겠습니다.

감사합니다.!

안녕하세요. 회사와 함께 성장하고 싶은 KOSE입니다.

이번 포스팅은 프로그매러스 광고 삽입 자바 풀이를 작성하고자 합니다.

문제 출처:  https://school.programmers.co.kr/learn/courses/30/lessons/72414#

1. 풀이 소스 

import static java.lang.Integer.parseInt;

class Solution {
    public String solution(String play_time, String adv_time, String[] logs) {
        
        if (play_time.equals(adv_time)) return "00:00:00";

        int[] allTime = new int[getSecondsTime(play_time) + 1]; // 00:00:00 ~ 00:00:02은 2개의 배열 공간 필요
        
        for (String log : logs) {
            String[] times = log.split("-");
            String sTime = times[0];
            String eTime = times[1];
            
            int start = getSecondsTime(sTime);
            int end = getSecondsTime(eTime);
            
            allTime[start] += 1; // 누적합을 위한 시작 지점 
            allTime[end] -= 1; // 누적합을 위한 마지막 지점에 -1  // 00:00:00 ~ 00:00:02 [1, 1, 0] (00:00 ~ 00:01, 00:00)
        }
        
        for (int i = 1; i < allTime.length; i++) {
            allTime[i] = allTime[i - 1] + allTime[i]; // 이전항에 누적합으로 더함 (00:00:00 ~ 00:00:10)
        }     
        
        int advTime = getSecondsTime(adv_time); // 00:00:00 ~ 00:00:02 (2초)
        long sum = 0;
        
        for (int i = 0; i < advTime; i++) { // advTime이 2초 하면 
            sum += allTime[i];  // ex) 0초부터 ~ 2초까지 누적합을 계산 [1, 1, 0] -> 2
        }
                
        int idx = advTime; // 시작점을 advTime 으로 설정 (2)
        long maxSum = sum; // 가장 큰 토탈 시간
        int startPoint = 0; // 가장 큰 토탈 시간에 맞는 포인트 
        int startCnt = 0; // 누적합에서 포인터를 이동시킬 cnt
        
        // idx = 3, 3초까지의 누적합 0 ~ 1초까지의 누적합 
        for (int i = idx; i < allTime.length; i++) {
            
            sum = sum + allTime[i] - allTime[startCnt]; 
            startCnt++; // 누적합에서 빠진 인덱스이므로 시작 포인트를 위해 ++
            
            if (maxSum < sum) {
                maxSum = sum;
                startPoint = startCnt; // 시작점은 누적합에 포함되기 시작한 (= 누적합에서 빠진 마지막 인덱스)   
            }
        }
        
        return getTime(startPoint);
    }
    
    private int getSecondsTime(String times) {
        String[] time = times.split(":");
        return parseInt(time[0]) * 60 * 60 + parseInt(time[1]) * 60 + parseInt(time[2]);
    }
    
    private String getTime(int point) {
        int hour = point / 3600;
        int minute = (point % 3600) / 60;
        int seconds = (point % 3600) % 60;
            
        return getStringTime(hour) + ":" + getStringTime(minute) + ":" + getStringTime(seconds);
    }
    
    private String getStringTime(int time) {
        String result = "";
        if (time < 10) result = "0" + String.valueOf(time);
        else result = String.valueOf(time);
        return result;
    }
}

2. 풀이 과정

해당 문제는 이전에 풀었던 문제인 누적합 개념을 적용하면 보다 빠르게 해결할 수 있습니다.

누적합이란 임의의 점이 n ~ m까지 범위이고 특정 범위로 시작점 끝점이 주어질 때,

매번 for문으로 주어진 범위까지 1씩 증가하면서 반복해서 더하는 것이 아니라, 주어진 시작점과 끝점에 포인트를 기록하여 

단 한 번의 포문으로 누적합이 될 수 있도록 구현하는 방법입니다.

예를 들면 다음과 같습니다.

int[] point = {4, 8};
int[] arr = new int[10];

for (int i = point[0]; i <= point[1]; i++) {
    arr[i] += 1;
}


int[] arr2 = new int[10];

arr2[point[0]] += 1;
arr2[point[1] + 1] -= 1;

for (int i = 1; i < arr2.length; i++) {
    arr2[i] = arr2[i] + arr2[i - 1];
}

위의 예시는 누적합을 적용하지 않은 개념으로 범위 계산 시 매번 해당 범위사이에 있는 값을 +1 해야 합니다.

하지만 누적합은 누적할 범위 시작점에 +1, 마지막 점 + 1에 -1을 해줌으로써 누적합을 구현할 수 있습니다.

최종적으로 누적합을 계산하면 둘 다 5가 나옵니다. 만약 구해야 하는 point가 10만 개이고, 범위가 최대 1000만이라면
앞 서 하나씩 1을 증가시켜서 누적합을 계산하는 경우 최악은 10만 * 범위(1000만) 까지의 시간 복잡도가 나옵니다.

반면, 누적합을 구하는 경우 point 시작점, 끝점 계산은 2개가 소요되고, 마지막 누적합만 적용하면 되므로

2 * 10만 + 1000만의 시간 복잡도가 소모됩니다.

따라서, 이 원리를 적용하여 해당 문제를 해결하려면 범위 계산을 위해 각 영상 시작 시간과 종료시간을 모두 초 단위로 바꿔야 합니다. 

예를 들어 "01:00:00 - 01:01:00" 은 초단위로 설정하면 3600 * 1  ~ 3600 * 1 + 60 * 1입니다.

즉 영상 시작이 0초대에 시작한다고 하면 영상 시작으로 3600초 ~ 3660 사이입니다. 

그렇다면 해당 영상 누적 합을 위해 범위를 어떻게 설정해야 할까요?

0 ~ 1초까지의 누적시간은 1초입니다. 이 1초를 어느 위치에 선정하느냐에 따라 접근 방식이 달라질 수 있습니다.

저는 누적 시간이 가장 크면서 가장 빠른 시간을 구해야 하므로,

0 ~ 1초 사이의 누적합 1초는 인덱스 0에 기록하는 방법을 택했습니다.

즉, [0, 0, 0] (0 ~ 3초)의 영상 시간에 광고가 0 ~ 1초 동안 지속한다면, 

[1, -1, 0]로 누적합을 위한 배열 A를 설정하고, 최종 누적합으로 인한 계산은 [1, 0, 0]이 나옵니다.

이를 이용하여, 누적합을 계산한 후,

for문으로 다음 인덱스와 시작점 인덱스를 옮긴 후, 고정된 K 범위 내에서 가장 많은 누적시간을 기록한 startPoint를 찾습니다.

오름차순으로 for문 인덱스를 설정하는 경우 이전 maxSum과 sum을 비교하여 sum이 더 큰 경우를 찾는다면 가장 빠른 startPoint를 찾을 수 있습니다.

테스트 케이스 공유 : 

"99:59:59" "00:00:01" ["69:59:59-89:59:59", "01:00:00-21:00:00", "79:59:59-99:59:59", "11:00:00-31:00:00"] "11:00:00"

"00:00:10"  "00:00:09"  ["00:00:00-00:00:03", "00:00:03-00:00:04", "00:00:03-00:00:05", "00:00:09-00:00:10"]  "00:00:00"

"00:00:10"  "00:00:09"   ["00:00:01-00:00:03", "00:00:03-00:00:04", "00:00:03-00:00:05", "00:00:09-00:00:10", "00:00:09-00:00:10"] "00:00:01"

"00:00:10"  "00:00:07"  ["00:00:02-00:00:03", "00:00:03-00:00:04", "00:00:03-00:00:05"]  "00:00:00"

"00:00:10" "00:00:01" ["00:00:01-00:00:02", "00:00:03-00:00:04", "00:00:03-00:00:05"] "00:00:03"

"00:00:10" "00:00:01" ["00:00:01-00:00:02", "00:00:03-00:00:04", "00:00:02-00:00:05"] "00:00:03"

"00:00:10" "00:00:02" ["00:00:01-00:00:02", "00:00:02-00:00:04", "00:00:02-00:00:05"] "00:00:02"

"50:00:00" "49:50:00" ["15:36:51-38:21:49", "10:14:18-15:36:51", "38:21:49-42:51:45"] "00:00:00"

이상으로 해당 문제 풀이를 마치도록 하겠습니다. 감사합니다.!!

안녕하세요. 회사와 함께 성장하고 싶은 KOSE입니다.

이번 포스팅은 프로그래멋 110 옮기기 자바 풀이를 작성하고자 합니다.

문제 출처: https://school.programmers.co.kr/learn/courses/30/lessons/77886

해당 문제는 풀지 못하여 블로그를 참고하여 코드를 작성하였고 이에 대한 방법을 주석화하여 정리하였습니다.

1. 풀이 소스 

import java.util.*;

class Solution {
    public String[] solution(String[] s) {
        String[] answer = new String[s.length]; // 정답 배열 설정
        StringBuilder sb; 
        
        for (int i = 0; i < s.length; i++) {
            String str = s[i]; 
            Stack<Character> stack = new Stack<>(); 
            
            int cnt = 0; // 연속된 캐릭터 타입의 값이 110인 것의 개수 
            
            for (int j = 0; j < str.length(); j++) {
                char z = str.charAt(j); // 스택이 2 이상 && z가 0이라면 스택에서 두개를 빼서  110 비교
                
                if(z == '0' && stack.size() >= 2) {
                    char y = stack.pop(); 
                    char x = stack.pop();  
                    
                    if (x == '1' && y == '1' && z == '0') {
                        cnt++; 
                    } else {
                        stack.push(x);  // 110이 아니라면 다시 후입 선출을 위해 x y z 순으로 스택에 넣기
                        stack.push(y);
                        stack.push(z);
                    }
                } else {
                    stack.push(z); // 스택 사이즈가 2보다 작다면 z가 1이더라도 스택에서 빼서 110을 만들 수 없으므로
                }     
            }
            
            int idx = stack.size(); // idx는 stack 사이즈 (연속 수가 110이 아닌 경우 스택에 다 넣음)
            
            sb = new StringBuilder();
            
            // 참조1
            boolean flag = false; // 맨 처음 0이 위치하는 지점 전까지 idx를 감소하기 위함 하단에 예시
            
            while(!stack.isEmpty()) {
                if (!flag && stack.peek() == '1') idx--;
                
                if (!flag && stack.peek() == '0') flag = true;  // 스택에서 뺀 값이 0이라면 0 자리에 위치
                
                sb.insert(0, stack.pop()); // sb에 정순으로 입력함으로써 원래 문자열에서 110만 뺀 상태
            }
            
            if (cnt > 0) { // 110 개수가 양수라면
                while (cnt > 0) {
                    sb.insert(idx, "110"); // 스택에서 뺄 때 (역순이므로 나중에 나오는 값이 앞쪽) 0이 나오는 다음의 인덱스
                    idx += 3; // 3개를 추가했으므로 +3
                    cnt --; // cnt--
                }
                answer[i] = sb.toString();
            } else {
                answer[i] = s[i]; // 만약 추가할 110이 없다면 문자열 그대로 리턴
            }
        }
        return answer;
    }

}

2. 풀이 중점 사항

해당 문제의 중요한 포인트는 stack을 활용하여 문자열 탐색을 합니다. 110이 나온다면 카운트를 증가시키고 그 외의 문자열은 모두 스택에 넣습니다. 사전순 정렬을 이용한다면 110은 10, 0보다 앞서 있을 수 없습니다. 

즉 0이 나오는 시점 마지막 시점의 바로 뒤에 위치한다면 00000101000 110 11111 사전순 정렬에서 앞에 만들 수 있습니다.

이를 구현하기 위한 자료는 참고#1입니다.

가령 문자열이 다음과 같이 있습니다.

문자열: 11010111 

먼저 문자열을 탐색하여 110이 있다면 카운트를 증가시키고 연속된 숫자로 110이 아니라면 모두 스택에 넣습니다.

cnt = 1

stack : 10111        (후입 선출로 인덱스 4가 이 먼저 출력)

idx = 5 (stack size)

boolean flag = false // 해당 flag는 문자열에서 가장 마지막의 0, 스텍 기준으로는 가장 빠른 0이 나오면 true로 바꿈

sb.insert(0, stack.pop()) 스텍에서 나온 문자열을 정순으로 배치하기 위해 놓습니다.

시뮬레이션을 해보면 

sb = 111

stack : 10

flag = false

idx = 2

cnt = 1

sb = 0111

stack = 1 

flag = true

idx = 2

cnt = 1

sb = 10111

stack : x

flag = true

idx = 2

cnt = 1

cnt > 0 이므로 idx의 위치인 10111 의 10 <1> 11에 110을 추가합니다.

10110111 이렇게 설정하게 되면 문자열 기준으로 사전 순 정렬에서 더 빠른 정렬을 만들 수 있습니다.

만약 101이더라도 101101을 만들어야 하는데, 그 이유는 110을 사전순 정렬을 위해 잠시 빼놓았을 뿐 반드시 써야 하기 때문에

1이 하나더라도 1101로 만들면 이전 최초 문자열보다 더 빠른 문자열을 만들 수 있습니다.

최초 11010111 

변경 10110111

나머지 자세한 사항은 주석화 하였습니다.

이상으로 문제 풀이를 마치도록 하겠습니다. 감사합니다.!

참고 출처: https://wellbell.tistory.com/228

안녕하세요. 회사와 함께 성장하고 싶은 KOSE입니다.

이번 문제는 프로그래머스 모두 0으로 만들기 자바 풀이를 작성하도록 하겠습니다.

문제 출처: https://school.programmers.co.kr/learn/courses/30/lessons/76503#

1. 풀이 소스

import java.util.*;

class Solution {
    public long solution(int[] a, int[][] edges) {
        Graph graph = new Graph(a);
        
        if (graph.isInitEnd() == 0 || graph.isInitEnd() == -1) {
            return graph.isInitEnd(); // 0 또는 -1 종료 조건
        }
        
        graph.addEdge(edges); // graph에 edge 설정
        graph.dfs(0);      
        
        return graph.getAnswer();
    }
}

class Graph {
    
    Node[] nodes; // 노드 배열
    boolean[] visited; // 방문 여부
    long answer; // 정답 long 타입!
    boolean isAllZero; // 모두 0인지 아니면 어떤 수는 0이 아닌지로 종료 여부 체크
    long isPossibleSumZero; // 합이 0이 가능한지 체크
    
    class Node {
        int x;
        long w;
        List<Node> adjacent = new ArrayList<>();
        
        Node (int x, long w) {
            this.x = x;
            this.w = w;
        }
    }
    
    Graph(int[] arr) {
        nodes = new Node[arr.length]; // 노드 배열
        visited = new boolean[arr.length]; // 방문 여부 체크
         
        for (int i = 0; i < nodes.length; i++) {
            nodes[i] = new Node(i, arr[i]); // 노드 생성
            if (arr[i] != 0) this.isAllZero = false; // 하나라도 0이 아니라면 어떤 수는 0이 아니므로 false
            isPossibleSumZero += arr[i]; // 모든 수의 합이 zero가 될 수 있는지 체크
        }
        
    } 
    
    
    int isInitEnd() {
        if (isPossibleSumZero != 0) return -1; // 모든 수의 합이 0이 안된다면 조료
        if (this.isAllZero) return 0; // 이미 모든 수가 0이라면 종료
        return 1; 
    }
    
    void addEdge(int[][] edges) {
        
        for (int i = 0; i < edges.length; i++) {
            int u = edges[i][0]; // edge 설정
            int v = edges[i][1];
            
            Node n1 = nodes[u];
            Node n2 = nodes[v];
            
            n1.adjacent.add(n2); // 양방향 연결관계
            n2.adjacent.add(n1);
        }
    }
    
    long dfs(int x) {
        
        visited[x] = true; // 방문 체크
        
        Node node = nodes[x]; // 노드 설정
        
        for (int i = 0; i < node.adjacent.size(); i++) {
            Node adjacent = node.adjacent.get(i); // 인접한 노드 가져옴
            
            if (!visited[adjacent.x]) {
                node.w += dfs(adjacent.x); // dfs로 인접한 노드로부터 가중치를 업데이트하여 가져옴 --> 중간 노드가 선택된다면 리프노드로 계속 방문하여 w 업데이트 
            }
        }
        
        this.answer += Math.abs(node.w); // 노드의 가중치의 절대값을 더함 (- 혹은 + 도 0으로 만들기 위해서는 정량적인 수가 필요하므로)
        
        return node.w; // 노드의 가중치를 리턴하여 dfs
    }
    
    
    long getAnswer() {
        return this.answer;
    }
    
}

2. 풀이 과정

해당 문제는 연결된 트리가 zeroSum을 통해 0이 될 수 있는지 판별할 수 있는 조건이 필요했습니다.

이를 위해 모든 수의 합이 0이 된다면, 연결위치에 상관없이 모두 0으로 만들 수 있다는 사실에 근거하여,

먼저 isPossibleSumZero가 가능한지 판별하였습니다.

또한 모두 0인지 판단하기 위한 조건을 isAllZero를 추가하여 조기 종료가 수행될 수 있도록 하였습니다.

핵심 로직은 dfs를 이용하여 풀이를 했습니다. 

          1 -- 1 -- 1 -- 1
          |
 -9  -- 1 -- 2 
  |     |   

  0     2

이와 같은 트리 구조가 있다고 가정하겠습니다.

dfs로 0번째 인덱스를 선택했을 때, 0이 선택된다면 인접한 노드를 검색합니다. 

인접한 노드 1(가중치 -9)를 선택하게 되면서 노드 1에 대한 dfs를  진행합니다. 

즉, 노드 1의 인접한 노드인 노드 2(가중치 1)를 찾은 후 다시 dfs를 적용하는 방식으로 재귀적 호출로 최종 리프(루트) 노드에 도달하게 된다면, 더 이상 방문할 노드가 없으므로 answer를 업데이트하고 node.w를 리턴하며 재귀적으로 node.w가 업데이트하게 됩니다,

최종적으로 answer를 리턴하면 됩니다.

해당 문제에 대한 테스트 케이스를 추가로 작성하였는데 공유드리겠습니다.

//        1 -- 1 
//        |
// -7  -- 1 -- 2
//  |     |
//  0     2
//  

// 7 + 2 + 4  = 14


//        1 -- 1 -- 1 -- 1
//        |
// -9  -- 1 -- 2 
//  |     |    
//  0     2


//  9 + 2 + 2 + 1 + 2 + 3 + 4  = 23


//                              -2
//                             /
//   2 -- 2 -- 2       -8 -- -7 -- -2 
//              \     /  \
//    3 -- 2 -- 8 -- 7    -2 -- -3
//                          \
//                           -2
// 92

테스트 케이스 

[-7, 0, 2, 1, 2, 1, 1], [[0, 1], [3, 4], [2, 3], [0, 3], [5, 3], [6, 5]], 14

[-9, 0, 2, 1, 2, 1, 1, 1, 1], [[0, 1], [3, 4], [2, 3], [0, 3], [5, 3], [6, 5], [7, 6], [8, 7]], 23

[-9, 0, 2, 1, 2, 1, 1, 1, 1, -18, 18]. [[0, 1], [3, 4], [2, 3], [0, 3], [5, 3], [6, 5], [7, 6], [8, 7], [9, 0], [10, 2]], 95

[2, 2, 2, 3, 2, 8, 7, -8, -7, -2, -2, -2, -3, -2], [[0, 1], [1, 2], [3, 4], [4, 5], [2, 5], [5, 6], [6, 7], [7, 8], [8, 9], [8, 10], [7, 11], [11, 12], [11, 13]], 92

이상으로 해당 문제 풀이를 마치겠습니다.! 감사합니다.

안녕하세요. 회사와 함께 성장하고 싶은 KOSE입니다.

이번 포스팅은 프로그래머스 주차 요금 계산에 대한 글을 작성하고자 합니다.

문제 출처: https://school.programmers.co.kr/learn/courses/30/lessons/92341

1. 풀이 소스

import java.util.*;
import static java.lang.Integer.parseInt;

class Solution {
    public int[] solution(int[] fees, String[] records) {
        Parking park = new Parking(fees); // 인스턴스 생성
        return park.apply(records);
    }   
}

class Parking {
    static int basicTime; // 기본 제공 시간
    static int basicFee; // 기본 요금
    static int unit; // 단위 시간
    static int unitFee; // 단위 요금
    static final int LAST_TIME = 1439; // 1380 + 59 = 1439 (23:59)
    
    Map<String, ParkFee> map = new HashMap<>(); // 차량 번호 기록 map
    
    class ParkFee {
        int inTime; // 입차
        int usedTime; // 누적 사용 시간

        ParkFee(int inTime) {
            this.inTime = inTime;
        }
    }
    
    Parking(int[] fees) { // 초기화
        basicTime = fees[0];
        basicFee = fees[1];
        unit = fees[2];
        unitFee = fees[3];
    }
    
    void add(String carNumber, int inTime) { // time: 분으로 설정된 시간
        if (map.containsKey(carNumber)) { 
            ParkFee parkFee = map.get(carNumber); // 차량 시간이 있다면 intime 값 변경
            parkFee.inTime = inTime;
        } else map.put(carNumber, new ParkFee(inTime)); // 없다면 인스턴스 생성
    }
    
    int out(String carNumber, int outTime) {     
        ParkFee parkFee = map.get(carNumber);
        int inTime = parkFee.inTime;
        parkFee.inTime = -1;  // 00:00의 경우 inTime이 0이므로 -1로 설정
        return outTime - inTime; // 출차 - 입차 시간 계산
    }
    
    int calFee(int usedTime) {
        if (usedTime <= basicTime) return basicFee; // 만약 기본 제공 시간보다 적은 경우 기본 요금
        int additionalTime = (usedTime - basicTime) % unit == 0 ?  (usedTime - basicTime) / unit : ((usedTime - basicTime) / unit) + 1;   // 단위 계산을 위한 올림 계산
        return basicFee + additionalTime * unitFee; // 기본 요금 + 추가 시간 * 단위 비용
    }
    
    
    int[] apply (String[] records) {
        for (String record : records) {
            String[] rc = record.split(" ");
            String[] timeZone = rc[0].split(":");
            int time = parseInt(timeZone[0]) * 60 + parseInt(timeZone[1]);
            
            String carNumber = rc[1];
            boolean in = rc[2].equals("IN");
            
            if (in) add(carNumber, time);
            
            else {
                ParkFee parkFee = map.get(carNumber);
                parkFee.usedTime += out(carNumber, time); // 출차 - 입차로 누적 시간 업데이트
            }          
        }
        
        List<String> keys = new ArrayList<>();
        keys.addAll(map.keySet()); // ketSet (차 번호) 모두 keys에 업데이트
        keys.sort(Comparator.comparing(s -> s)); // 차 번호로 정렬
        
        int[] result = new int[keys.size()];
        
        for (int i = 0; i < keys.size(); i++) {
            ParkFee parkFee = map.get(keys.get(i));
           
            int fee = 0;
            if (parkFee.inTime != -1) {
                parkFee.usedTime += LAST_TIME - parkFee.inTime; // 누적 시간 업데이트
            } 
            
            result[i] = calFee(parkFee.usedTime); // 누적시간으로 금액 계산
        }
        
        return result;
    }
}

2. 풀이 과정

해당 문제는 inTime, outTime을 설정할 때, 누적 시간을 체크해야 하는 부분이 있습니다.

즉, 여러 번 입차 및 출차하였더라도 누적 시간으로 금액을 측정해야하므로 ParkFee라는 객체에 누적 시간을 더하는 usedTime을 적용하여, 출차 시 출차 - 입차 시간을 더하는 과정을 수행하였습니다.

처음에 실수한 부분은 "00:00"은 시간 * 60 + 분 설정에 의하면 0이 나옵니다. 여기서 출차 후 inTime을 0으로 설정하게 되면,
해당 값이 00:00에 입차를 하여 출차가 된 것인지 아니면 아직 출차가 안된 채로 남아있는지 구분이 어려울 수 있습니다.따라서, -1로 설정하여 구분하도록 하였고 마지막에 calFee로 요금을 계산하는 과정을 처리하였습니다.

자세한 사항은 주석으로 표기하였습니다.

감사합니다.!

안녕하세요. 회사와 함께 성장하고 싶은 KOSE입니다.

이번 포스팅은 프로그래머스 표 병합을 자바로 푼 과정을 정리하도록 하겠습니다.

문제 출처:  https://school.programmers.co.kr/learn/courses/30/lessons/150366 

1. 풀이 소스

import java.util.*;
import static java.lang.Integer.parseInt;

class Solution {
    public String[] solution(String[] commands) {
        Matrix matrix = new Matrix();
        return matrix.apply(commands);
    }
}

class Matrix {
    static final int RANGE = 2501;
    
    int[] parent = new int[RANGE]; // 인덱스에 부모 인덱스를 넣기위한 일차원 배열
    String[] values = new String[RANGE]; // 셀의 값을 넣기 위한 배열
    
    Matrix() { // 초기화
        for (int i = 1; i < RANGE; i++) {
            parent[i] = i;
            values[i] = "";
        }
    };
    
    int find(int a) { // 재귀로 루트 인덱스를 찾기 위한 과정
        if (parent[a] == a) return a; // 만약 루트 노드가 없다면 자기 자신 인덱스 이므로 리턴
        else return parent[a] = find(parent[a]); // 재귀 시작 후 ex a[1] = 3 -> a[3] = 4 -> a[4] = 4 라면 종료 후 4 반환
    }
    
    void union(int a, int b) {
       if (a != b) parent[b] = a; // parent[b] = a 로 설정하면서 union 실행
    }
    // parent[7] = 4 --> parent[13] 즉 리프 노드부터 parent[4] = 4 까지 연결됌
    
    int convertIndex(int row, int col) {
        return 50 * (row - 1) + col; // row = 1, y = 1 -> 1 // row = 2, y = 1 -> 51
    }
    
    void update(int r, int c, String value) {
        int idx = convertIndex(r, c);
        values[find(idx)] = value; // 루트 노드를 찾아서(find) 반환 후 루트 노드의 values를 value 변경
    }
    
    void update(String before, String after) {
        for (int i = 1; i < RANGE; i++) {
            if (before.equals(values[i])) values[i] = after; // 루트 노드가 기록되므로 루트 노드의 value를 변경
        }
    }
    
    void merge(int r1, int c1, int r2, int c2) {
        
        if (r1 == r2 && c1 == c2) return; // 병합할 위치가 동일하면 종료 
        
        int idx1 = convertIndex(r1, c1); // 병합할 대상
        int idx2 = convertIndex(r2, c2); // 병합될(할) 대상
        
        int root1 = find(idx1); // 병합할 대상의 루트 노드 번호
        int root2 = find(idx2); // 병합될(할) 대상의 루트 노드 번호
        
        if (root1 == root2) return; // 두 루트 노드가 같다면 이미 병합되어 있는 노드임 
        
        String root = values[root1].isBlank() ? values[root2] : values[root1]; // root1의 값이 "" 라면, root2를 기준으로 병합
        values[root2] = ""; // root2는 값이 있더라도, root1을 기준으로 병합될 예정이므로 ""
        
        union(root1, root2); // root1 으로 병합
        values[root1] = root; // root1의 value를 root1 혹은 root2가 values에 가지고 있던 값으로 업데이트
    }
    
    void unmerge(int r, int c) {
        int idx = convertIndex(r, c);
        int root = find(idx); // 인덱스가 연결된 루트 노드
        
        String rootValue = values[root];
        values[root] = ""; // 루트 노드에 값을 ""로 바꿈으로써 병합되어 있던 셀들이 값을 잃음
        values[idx] = rootValue; // 선택된 노드에 rootValue를 참조 (만약 값이 있다면 병합을 해제하면 해당 포인트가 값을 얻음)
        List<Integer> dels = new ArrayList<>();
        for (int i = 1; i < RANGE; i++) {
            if (find(i) == root) { // find(i)로 루트 노드로 연결된 노드를 전부 탐색
                dels.add(i); 
            }
        }
        for (Integer i : dels) {
            parent[i] = i; // 해당 인덱스를 자기 자신으로 바꿈으로써 연결 노드 전부 제거
        }
    }
    
    String print(int r, int c) {
        int idx = convertIndex(r, c); 
        int root = find(idx);
        
        if (values[root].isBlank()) return "EMPTY";
        return values[root]; // 루트 노드의 값을 출력 = 병합된 노드의 루트 노드의 값
    }
    
    String[] apply(String[] commands) {
        List<String> result = new ArrayList<>();
        
        for (String command : commands) {
            String[] cmds = command.split(" ");
            
            String cmd = cmds[0];
            String v1 = cmds[1];
            String v2 = cmds[2];
            
            if (cmds.length >= 4) {
                String v3 = cmds[3];
                if (cmds.length == 5) merge(parseInt(v1), parseInt(v2), parseInt(v3), parseInt(cmds[4])); // merge
                else update(parseInt(v1), parseInt(v2), v3); // update 오버로딩
            } else {
                if (cmd.equals("UPDATE")) update(v1, v2); // update 오버로딩
                else if (cmd.equals("UNMERGE")) unmerge(parseInt(v1), parseInt(v2)); // unmerge
                else result.add(print(parseInt(v1), parseInt(v2))); // print
            }
        }
        
        return result.toArray(new String[0]);
    }
    
}

2. 풀이 중점

해당 문제는 Union - Find를 활용하여 문제를 해결하는 방법이 있습니다. Union - Find 방법은 재귀적으로 루트 노드를 찾은 후 루트 노드끼리 병합하여 하나의 연결 관계를 만드는 방법입니다.

가령 다음의 배열이 있습니다.

a[0] = 0,  a[1] = 1,  a[2] = 2,  a[3] = 3

여기서 a[0] 과 a[1] 를 연결된 하나의 집합으로 만들고 싶다면 연결관계를 설정할 수 있는 배열을 하나 생성한 후 (p 배열)

p[0] = 1,  p[1] = 1 을 처리하여 0 번째 인덱스에 1을 넣음으로써 1이 루트 노드가 되고 두 노드는 재귀식으로 연결관계를 파악할 수 있습니다.

이 문제도 다음과 같이 find(), union() 메서드를 선언하여 먼저 재귀 방법으로 root 노드를 찾은 후, 두 root 노드를 병합하는 과정을 수행할 수 있습니다. 

이후, 병합 해제는 루트 노드를 찾은 후, 루트 노드의 value를 ""으로 처리하여 값을 지웁니다. 이후, 재귀로 루트 노드를 가리키는 노드를 찾기 위해 find(i)를 하여 루트 노드라면 해당 값을 자신의 인덱스로 업데이트 합니다.

자세한 설명은 다른 풀이와 마찬가지로 주석으로 처리하였습니다.!

이상으로 표 병합 문제를 마치도록 하겠습니다. 감사합니다.!!!

안녕하세요. 회사와 함께 성장하고 싶은 KOSE입니다.

이번 포스팅은 프로그래머스 미로 탈출 명령어 자바 풀이에 대해 작성하고자 합니다.

해당 문제는 카카오 채용 Lv3 문제로 많은 생각을 고려하는 문제였습니다.

최초 풀이는 BFS를 활용하였지만 메모리 초과가 발생하였습니다.

따라서, 보다 효과적으로 문제를 어떻게 풀이하면 좋을까 고민하다 문제를 자세히 읽어본 후 힌트를 얻을 수 있었습니다.

이전처럼 소스부터 정리한 후, 풀이 과정을 상세하게 정리하겠습니다.

문제 출처: 

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

1. 풀이 소스:

class Solution {
    
    Node node;
    int row; // 행 범위
    int col; // 열 범위
    int targetX; // 목표 x좌표
    int targetY; // 목표 y좌표
    int targetStep; // 만족해야하는 스텝 수
    
    public String solution(int n, int m, int x, int y, int r, int c, int k) {
        String answer = "";
        
        row = n + 1; 
        col = m + 1;
        targetX = r; 
        targetY = c;
        targetStep = k;
        node = new Node(x, y); // 출발 노드 설정
    
        while(node.step <= targetStep) {
            if (node.step == targetStep) {
                if (node.x == targetX && node.y == targetY) {
                    return node.answer;
                }
            }
            
            if (isPossibleD()) { // 아래로 갈 수 있는 조건을 만족한다면 x++ (행을 내려야 하므로 +)
                node.x++;
                node.answer += "d";
            } else if (isPossibleL()) { // 다음 우선 순위로 L 탐색 가능 확인
                node.y--;
                node.answer += "l";
            } else if (isPossibleR()) { // d, l로 갈 수 없다면 r 가능 여부 확인
                node.y++;
                node.answer += "r";
            } else if (isPossibleU()) { // 마지막 우선순위 u 확인
                node.x--;
                node.answer += "u";
            } else { // 위의 분기문을 먼저 고려한 결과 해당하지 않는다면 탈출
                answer = "impossible"; 
                break;
            }
            
            node.step++; // break되지 않았다면 어느 한 방향으로 움직였다는 의미이므로 step++
        }
        
        
        return answer;
    }
    
    
    class Node {
        int x;
        int y;
        int step;
        String answer = "";
        
        Node (int x, int y) {
            this.x = x;
            this.y = y;
        }
    }
    
    boolean isPossibleD() { // down은 행을 내려야하므로 +
        return node.x > 0 && node.x < row - 1 && isPossibleMove(node.x + 1, node.y);
    }
    
    boolean isPossibleU() { // up은 행을 올려야 하므로 -
        return node.x > 1 && (node.x < row) && isPossibleMove(node.x - 1, node.y);
    }
    
    boolean isPossibleL() { // left는 열을 왼쪽으로 가야하므로 -
        return node.y > 1 && node.y < col && isPossibleMove(node.x, node.y - 1);
    }
    
    boolean isPossibleR() { // right는 열을 오른쪽으로 가야하므로 +
        return node.y > 0 && (node.y < col - 1) && isPossibleMove(node.x, node.y + 1);
    }
    
    // 하단에 자세하게 설명하였습니다.
    boolean isPossibleMove(int x, int y) {
        return Math.abs(targetX - x) + Math.abs(targetY - y) + node.step + 1 <= targetStep;
    }
    
}

2. 풀이 방법

문제는 k개의 문자열의 길이를 반드시 유지하면서 사전 순으로 탐색하라고 되어있습니다. 이는 곧 갈 수 있는 거리가 여러 개 있더라도 탐색은 사전순으로 하라는 것을 의미합니다.

기존 BFS 혹은 DFS 탐색은 상하좌우 형태로 무작위로 실행하되 완전 탐색 혹은 백트래킹 형태로 진행됩니다.

하지만, 사전순으로 탐색을 하게 된다면 무조건 가깝게 갈 수 있다면 가깝게 이동하도록 구현할 수 있습니다.

가령 A - B까지 (10, 0) 만큼 차이가 있고 14번의 움직임이 필요하다면 

d * 10 + 이후 d - l - r - u로 움직이면 됩니다.

즉, 최대한 사전으로 움직일 수 있는 만큼 while문으로 움직이되 isPossibleMove라는 메서드에
다음에도 움직일 수 있는 범위가 유효한지 판단하기 위해  현재 step + 1과 목표 targetX, targetY (좌표)에서 현재 위치한 좌표를 빼서 타깃보다 같거나 작은 경우를 체크합니다.

이 제약 조건은 다음을 의미합니다.

만약, 해당 조건을 만족하지 않는 경우에는 예를 들어 최대 앞으로 움직일 수 있는 step이 10인데, 총거리가 10을 초과해 버리면 그 경로는 절대 목표점으로 갈 수가 없습니다.

따라서, while문으로 아래, 좌, 우, 위 방향으로 탐색을 진행하도록 하되, 해당 방향으로 이동했을 때 목표 step안에 도착할 수 없는 경로라면 if - else if - else 문으로 가능한 우선순위로 다시 움직이게 되고 전부 갈 수 없다면 else로 while문을 빠져나옵니다.

기타 자세한 풀이는 주석으로 설정하였습니다.

BFS 풀이 후 메모리 초과가 발생하여, 혹시 이 방법은 어떨까 불현듯 생각난 방법으로 풀었는데 한 번에 성공하여, 계속 꾸준히 알고리즘 문제를 푸니 정말 많이 성장했다는 점을 느끼게 되었습니다.

혹시 이 문제로 메모리 초과 혹은 시간초과가 발생하신다면, 저와 비슷한 방법으로 풀어보시면 좋을 것 같습니다.

이상으로 글을 마치도록 하겠습니다. 감사합니다.!!!

안녕하세요. 회사와 함께 성장하고 싶은 KOSE입니다.

이번 포스팅은 프로그래머스 - 두 큐 합 같게 만들기 자바 풀이를 정리하도록 하겠습니다.

문제 출처: https://school.programmers.co.kr/learn/courses/30/lessons/118667#

1. 풀이 소스:

import java.util.*;

class Solution {
    
    public int solution(int[] arr1, int[] arr2) {
        
        long arr1Sum = 0L; // 합을 위한 long 타입 초기화
        long arr2Sum = 0L;
        
        Queue<Integer> arr1Queue = new ArrayDeque<>();
        Queue<Integer> arr2Queue = new ArrayDeque<>();
        
        for (int i : arr1) {
            arr1Sum += i;
            arr1Queue.add(i);
        }
        for (int i : arr2) {
            arr2Sum += i;
            arr2Queue.add(i);
        }
        
        if (arr1Sum == arr2Sum) return 0; // 이미 합이 한 번에 같다면 종료
        
        EqualSum es = new EqualSum(arr1Sum, arr2Sum, arr1Queue, arr2Queue);
        
        return es.find();
    }

}

class EqualSum {
    
    int totalJob; // 최소 수행 과정
    int limit; // 무한 루프 제한 조건
    QueueSize big; // 합이 큰 Queue를 저장하려는 참조 QueueSize 인스턴스
    QueueSize small; // 합이 작은 Queue를 저장하려는 참조 인스턴스
    
    class QueueSize {
        long sum; // 합 저장
        Queue<Integer> queue; // 큐 참조
    
        QueueSize(long sum, Queue<Integer> queue) {
            this.sum = sum; 
            this.queue = queue;
        }  
    }
    
    EqualSum(long arr1Sum, long arr2Sum, Queue<Integer> arr1Queue, Queue<Integer> arr2Queue) {            
        if (arr1Sum >= arr2Sum) { // arr1Sum이 더 크면 big에 arr1Queue, small = arr2Queue
            big = new QueueSize(arr1Sum, arr1Queue);
            small = new QueueSize(arr2Sum, arr2Queue);         
            
        } else { // arr2Sum이 더 크다면 big에 arr2Queue 설정, small = arr1Queue
            big = new QueueSize(arr2Sum, arr2Queue);
            small = new QueueSize(arr1Sum, arr1Queue);
        }
        
        // 참조 #1
        limit = big.queue.size() * 3; // 한계치 설정을 위해 limit에 큐 크기 * 3 
    }
    
    void swap() { // 만약 queue에 있는 sum 크기가 달라진다면 swap으로 queue 참조 바꾸기
        QueueSize tmp = null; // swap을 위한 QueueSize tmp 생성
        if (big.sum < small.sum) {
            tmp = small;
            small = big;
            big = tmp;
        }
    }
    
    int find() {
        
        // 참조 #2
        while(!big.queue.isEmpty() && !small.queue.isEmpty()) { // 큐에서 더 이상 뺄 수 없는 경우 종료

            int pop = big.queue.poll(); // 합이 더 큰 queue에서 빼기
            small.queue.add(pop); // 작은 큐에 더하기
            
            big.sum -= pop; // 빅 큐 합 업데이트
            small.sum += pop; // 스몰 큐 합 업데이트
            totalJob++; // totalJob 업데이트
            
            if (big.sum == small.sum) return totalJob; // 두 큐의 합이 같다면 종료    
            if (big.sum < small.sum) swap(); // 만약 스몰 큐의 합이 더 크면 스왑
            
            if (totalJob > limit) break; // 큐 교체의 한계보다 더 크다면 무한 루프 해제
        }
        
        return -1; // 두 큐의 합을 같게 만들 수 없음
    }
}

2. 풀이 과정

해당 문제는 Queue1, Queue2에 대한 참조를 바꿔가며 합이 더 큰 큐에서 작은 큐로 이동하여 합을 비교하는 방식으로 문제를 풀이해야 합니다.

이러한 과정이 가능한 이유는 Big 큐는 Small 큐보다 무조건 크기 때문에 Big에서 Small 큐로 원소를 옮기다 보면
어느 순간 같게 되는 상황이 생길 수 있기 때문입니다.

예를 들면 아래의 테스트 케이스가 존재합니다.

Big : 1 100

Small: 1 98

Big : 100

Small: 1 98 1

하지만 Big Queue에서 Small Queue로 옮기다 보면 Small Queue가 더 커질 수 있습니다. 이 경우 Swap을 통해
참조를 바꿔주어야 합니다.

Big : 1 100 2

Small: 1 1 97

Big: 100 2

Small : 1 1 97 1

Big : 2

Small: 1 1 97 1 100

<Swap>

Big: 1 1 97 1 100

Small: 2

---- 진행 ----

Big: 1 100

Small: 2 1 1 97 이 완성됩니다.

3. 종료 조건 

주석 참조 #1, 참조#2는 무한 루프에 빠지지 않도록 종료하는 것입니다.

참조#2

Big: 1 5

Small: 1 1 

Big : 5

Small : 1 1 1

여기서 Big에서 하나 더 뺀다면 Big의 큐가 비워져 버립니다.

이를 고려하면 결국 다시 Small에서 Big을 스왑하고 Big에 Queue 참조를 옮겨야 합니다. 

Big : X (X는 Big의 원소의 합)

Small: Y(Y는 Small의 원소의 합)

Big: 0 

Small : Y + X  

X > Y 었으므로  원소의 합인 Y보다 Big에 옮겨지는 큐 원소는 모든 원소의 합 Y > (부분 원소 합)이 만족합니다. 따라서,

Big : Y 

Small : X 가 될 때까지 반복하게 됩니다. 

이 경우 스왑하면 다시 원점으로 돌아가게 되므로 종료 조건에 포함됩니다.

참조#1

Queue의 길이에 * 3인 이유는 아래의 케이스를 확인하면 볼 수 있습니다.

두 큐가 마지막 스왑하기 전까지 특정 원소는 한 번씩만 이동한다면 바뀔 수 있는 최대 경우는 하나씩 교체하는 것입니다.

(Q1.size = Q2.size = n일 때, Q1 -> Q2로 이동후 Q2 -> Q1에서 반절의 개수만큼 이동시 2n, 하나씩 교체를 하는 경우 3n)

Q1: 1 2 3

Q2: 4 5 6

Q1: 2 3

Q2: 4 5 6 1

Q1: 2 3 4

Q2: 5 6 1

Q1: 3 4

Q2: 5 6 1 2

Q1: 3 4 5

Q2: 6 1 2

Q1: 4 5 

Q2: 6 1 2 3

Q1: 4 5 6

Q2 : 1 2 3

추가로 루프에 빠지고 있지 않는지 확인하는 테스트 케이스를 제공하겠습니다.!

테스트 추가 : [1000, 1000], [500, 400], [-1] 

자세한 설명은 주석으로 처리하였습니다.!

이상으로 프로그래머스 두 큐 합 같게 만들기 풀이를 마치도록 하겠습니다. 감사합니다.!