[프로그래머스][Level.2] 두 큐 합 같게 만들기

나의 풀이보다 더 신박하고 좋은 방법을 찾게 되어 정리하려고 한다.

 

문제 풀이📝

---

투 포인터를 사용한 풀이

첫번째 큐와 두번째 큐를 합친 하나의 배열을 생성한다.

합친 큐에서, 첫번쨰 큐의 시작지점을 left, 두번째 큐의 시작 지점을 right로 설정하여 구간합을 구한다.

두 큐의 값이 같아질 때의 값인 half를 정의한다. (half = (queue1Sum + queue2Sum) / 2)

• 첫번째 큐의 합이 half와 같을 때
  • 두 큐의 합이 같아졌으므로 최소 이동 횟수를 반환한다.
• 첫번째 큐의 합이 half보다 클 때
  • left 포인터를 한 칸 오른쪽으로 옮긴다.
  • 첫번째 큐의 합을 옮긴 후의 구간 합으로 갱신한다.
• 첫번째 큐의 합이 half보다 작을 때
  • right 포인터를 한 칸 오른쪽으로 옮긴다.
  • 첫번째 큐의 합을 옮긴 후의 구간 합으로 갱신한다.

위의 과정을 반복하다가 left 포인터가 right포인터를 따라잡거나 right 포인터가 합친 큐의 길이를 벗어나면 반복문을 탈출한다.

반복문을 탈출했다는 것은 두 큐의 합을 같게 만들지 못했다는 것이므로 -1을 반환한다.

 

구현🛠️

public class Solution_두_큐_합_같게_만들기 {

    public int solution(int[] queue1, int[] queue2) {
        // 핵심: 두 큐를 하나로 합쳐서 binary search 수행
        int[] totalQueue = new int[queue1.length + queue2.length];
        long queue1Sum = 0;
        long queue2Sum = 0;

        for (int i = 0; i < queue1.length; i++) {
            int val = queue1[i];
            totalQueue[i] = val;
            queue1Sum += val;
        }

        for (int i = queue1.length; i < queue1.length + queue2.length; i++) {
            int val = queue2[i - queue1.length];
            totalQueue[i] = val;
            queue2Sum += val;
        }

        // early return - 합을 같게 만들기가 불가능한 상황
        if ((queue1Sum + queue2Sum) % 2 == 1) {
            return -1;
        }

        int count = 0;
        int left = 0;
        int right = queue1.length;
        long half = (queue1Sum + queue2Sum) / 2;
        // 반복문 탈출 -> 두 큐를 같게 만들 수 없는 상황
        while (left < right && right < totalQueue.length) {
            if (queue1Sum == half) {
                return count;
            } else if (queue1Sum > half) {
                queue1Sum -= totalQueue[left++];    // 첫번째 큐의 합이 더 크다 -> left 포인터 이동
            } else {
                queue1Sum += totalQueue[right++];   // 첫번쨰 큐의 합이 더 작다 -> right 포인터 이동
            }
            count++;
        }
        return -1;
    }
}

 

실행결과✅

테스트 1 〉	통과 (0.02ms, 73.2MB)
테스트 2 〉	통과 (0.02ms, 75MB)
테스트 3 〉	통과 (0.01ms, 69.9MB)
테스트 4 〉	통과 (0.02ms, 71.9MB)
테스트 5 〉	통과 (0.04ms, 66.1MB)
테스트 6 〉	통과 (0.04ms, 74.5MB)
테스트 7 〉	통과 (0.04ms, 71.1MB)
테스트 8 〉	통과 (0.05ms, 76.5MB)
테스트 9 〉	통과 (0.11ms, 79MB)
테스트 10 〉	통과 (0.21ms, 75MB)
테스트 11 〉	통과 (4.97ms, 87.7MB)
테스트 12 〉	통과 (3.62ms, 97.9MB)
테스트 13 〉	통과 (2.85ms, 93.6MB)
테스트 14 〉	통과 (2.89ms, 86.1MB)
테스트 15 〉	통과 (2.47ms, 96.1MB)
테스트 16 〉	통과 (2.59ms, 94.4MB)
테스트 17 〉	통과 (3.57ms, 87.6MB)
테스트 18 〉	통과 (5.44ms, 141MB)
테스트 19 〉	통과 (5.58ms, 124MB)
테스트 20 〉	통과 (14.74ms, 131MB)
테스트 21 〉	통과 (5.73ms, 136MB)
테스트 22 〉	통과 (14.67ms, 135MB)
테스트 23 〉	통과 (6.86ms, 131MB)
테스트 24 〉	통과 (6.81ms, 125MB)
테스트 25 〉	통과 (0.05ms, 73.2MB)
테스트 26 〉	통과 (0.05ms, 76.3MB)
테스트 27 〉	통과 (0.02ms, 86.2MB)
테스트 28 〉	통과 (4.02ms, 99.6MB)
테스트 29 〉	통과 (0.58ms, 73.6MB)
테스트 30 〉	통과 (4.10ms, 96.1MB)