두 큐 합 같게 만들기

문제 설명

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

풀이

기본적인 아이디어는 두 큐의 합이 같아질 때까지 합이 더 큰 큐에서 합이 더 작은 큐로 이동시켜준다는 것입니다.

예시로 주어진 아래 두 큐의 경우를 살펴보면 queue1의 합은 14, queue2의 합은 16입니다.

queue1 = [3, 2, 7, 2]
queue2 = [4, 6, 5, 1]

이때 합이 더 큰 쪽에서 합이 더 작은 쪽으로 이동시키는 알고리즘을 수행해보면,

# round 1
queue1 = [3, 2, 7, 2, 4] # 18
queue2 = [6, 5, 1] # 12

# round 2
queue1 = [2, 7, 2, 4] # 15
queue2 = [6, 5, 1, 3] # 15

2번의 라운드를 거치고 나면 두 큐의 합이 같아지는 것을 알 수 있습니다.

우리는 각 큐에 직접 pop/insert를 수행하는 대신 두 큐의 합을 계속 추적하면서 각 큐의 시작 지점 인덱스를 옮겨주는 방식으로 구현하려고 합니다.

이런 방식을 투 포인터 (two pointer) 알고리즘이라고 하며, 두 큐에 직접 pop/insert를 수행하는 것보다 더 효율적입니다.

queue = [3, 2, 7, 2, 4, 6, 5, 1]

L = 0, LSum = 14
R = 4, RSum = 16

queue1과 queue2 두 개를 합친 새로운 큐, queue를 만든 뒤 각 큐의 시작 지점을 L, R로 선언하고 각각의 합을 구해줬습니다.

이제 각 라운드를 진행하고 나면 어떻게 되는지 살펴봅시다.

# round 1
# queue2에서 pop한 뒤, queue1에 insert해주는 것은 마치 R 포인터를 오른쪽으로 하나 옮기는 것과 동일합니다.
L = 0, LSum = 18
R = 5, RSum = 12

# round 2
# queue1의 합이 더 크므로 queue1에서 pop한 뒤, queue2로 insert 해줬습니다.
# 이는 L 포인터를 오른쪽으로 하나 옮기는 것과 같습니다.
L = 1, LSum = 15
R = 5, RSum = 15

여기서 조심해줘야되는 부분은 L 혹은 R 포인터를 이동시킬 때 queue의 길이를 벗어날 수 있다는 점입니다.
그러므로 포인터를 이동시킬 때 항상 queue의 길이만큼 mod를 취해줘서 값이 올바른 범위를 벗어나지 않도록 해줘야 합니다.

이제 코드를 살펴보겠습니다.

public int solution(int[] queue1, int[] queue2) {
        int N = queue1.length;

        int[] queue = new int[2 * N];
        System.arraycopy(queue1, 0, queue, 0, N);
        System.arraycopy(queue2, 0, queue, N, N);

        long LSum = 0;
        for (int i : queue1) {
            LSum += i;
        }

        long RSum = 0;
        for (int i : queue2) {
            RSum += i;
        }

        int L = 0;
        int R = N;

        int moves = 0;

        while (moves <= 4 * N) {
            if (LSum == RSum) {
               return moves;
            } else if (LSum > RSum) {
                LSum -= queue[L];
                RSum += queue[L];

                L = (L + 1) % queue.length;
            } else {
                LSum += queue[R];
                RSum -= queue[R];

                R = (R + 1) % queue.length;
            }

            moves++;
        }

        return -1;
    }

코드를 순서대로 살펴보면

1. 두 큐를 합친 새로운 큐, queue를 만들어줍니다.
2. 이전 큐의 합, LSum과 RSum을 구합니다.
3. 큐의 합을 비교하여, 포인터를 이동시키는 연산을 수행합니다. 이때 위에서 말했듯이 전체 큐의 길이 범위를 벗어나지 않도록 mod를 취해줍니다.

시간/공간 복잡도

시간 복잡도의 경우 worst case에 4 N 만큼의 연산을 수행하므로 O(N)이 됩니다. (N은 큐의 길이)
공간 복잡도의 경우 queue를 생성하기 위해 2 N 만큼의 공간을 사용하므로 역시 O(N)이 됩니다.