문제

길이가 같은 두 개의 큐가 주어집니다. 하나의 큐를 골라 원소를 추출(pop)하고, 추출된 원소를 다른 큐에 집어넣는(insert) 작업을 통해 각 큐의 원소 합이 같도록 만들려고 합니다. 이때 필요한 작업의 최소 횟수를 구하고자 합니다. 한 번의 pop과 한 번의 insert를 합쳐서 작업을 1회 수행한 것으로 간주합니다.

큐는 먼저 집어넣은 원소가 먼저 나오는 구조입니다. 이 문제에서는 큐를 배열로 표현하며, 원소가 배열 앞쪽에 있을수록 먼저 집어넣은 원소임을 의미합니다. 즉, pop을 하면 배열의 첫 번째 원소가 추출되며, insert를 하면 배열의 끝에 원소가 추가됩니다. 예를 들어 큐 [1, 2, 3, 4]가 주어졌을 때, pop을 하면 맨 앞에 있는 원소 1이 추출되어 [2, 3, 4]가 되며, 이어서 5를 insert하면 [2, 3, 4, 5]가 됩니다.

다음은 두 큐를 나타내는 예시입니다.

queue1 = [3, 2, 7, 2]
queue2 = [4, 6, 5, 1]
두 큐에 담긴 모든 원소의 합은 30입니다. 따라서, 각 큐의 합을 15로 만들어야 합니다. 예를 들어, 다음과 같이 2가지 방법이 있습니다.

queue2의 4, 6, 5를 순서대로 추출하여 queue1에 추가한 뒤, queue1의 3, 2, 7, 2를 순서대로 추출하여 queue2에 추가합니다. 그 결과 queue1은 [4, 6, 5], queue2는 [1, 3, 2, 7, 2]가 되며, 각 큐의 원소 합은 15로 같습니다. 이 방법은 작업을 7번 수행합니다.
queue1에서 3을 추출하여 queue2에 추가합니다. 그리고 queue2에서 4를 추출하여 queue1에 추가합니다. 그 결과 queue1은 [2, 7, 2, 4], queue2는 [6, 5, 1, 3]가 되며, 각 큐의 원소 합은 15로 같습니다. 이 방법은 작업을 2번만 수행하며, 이보다 적은 횟수로 목표를 달성할 수 없습니다.
따라서 각 큐의 원소 합을 같게 만들기 위해 필요한 작업의 최소 횟수는 2입니다.

길이가 같은 두 개의 큐를 나타내는 정수 배열 queue1, queue2가 매개변수로 주어집니다. 각 큐의 원소 합을 같게 만들기 위해 필요한 작업의 최소 횟수를 return 하도록 solution 함수를 완성해주세요. 단, 어떤 방법으로도 각 큐의 원소 합을 같게 만들 수 없는 경우, -1을 return 해주세요.

제한 사항

1 ≤ queue1의 길이 = queue2의 길이 ≤ 300,000
1 ≤ queue1의 원소, queue2의 원소 ≤ 10^9
주의: 언어에 따라 합 계산 과정 중 산술 오버플로우 발생 가능성이 있으므로 long type 고려가 필요합니다.

입력

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

출력

2

내가 했던 풀이 방법

1. queue1과 queue2를 합친 queue3 배열을 만든다.
2. queue1의 모든 요소의 합과 queue2의 모든 요소의 합을 sum1, sum2에 저장하고, sum1과 sum2의 합을 sum에 저장한다.
3. pointer1을 0, pointer2는 N로 초기화한다. queue3 배열에서 0번째 인덱스부터 N-1까지가 queue1의 요소이고 N부터 2×N-1까지가 queue2의 요소이다. pointer1이 1이 되면 queue1에 있는 요소가 pop이 되어 queue2에 마지막 요소로 insert되었음을 의미한다. 반대로 pointer2가 N+1이 되면 queue2에 있는 요소가 pop되어 queue1에 마지막 요소로 insert되었음을 의미한다.
4. 두 큐의 합이 같아진다는 의미는 queue1의 합이 sum/2가 된다는 의미이다. 즉, 반복을 통해 queue1의 합이 sum/2이 될 때까지의 count를 return 해주면 된다는 의미이다. sum1이 sum/2보다 작다면 pointer2의 맨 앞 데이터를 가져와 sum1에 더해주고, sum/2보다 크다면 pointer1의 맨 앞 데이터를 제거하고 sum1에서 빼주면 된다. 매번 반복할 때마다 count를 1 증가시켜준다. 만약 queue3.length×2만큼 count가 커지면 모든 요소를 다 제거하고 더해줘도 두 큐의 합을 같게 만들 수 없다는 의미이므로, 반복문을 탈출하고 -1을 return 한다.

코드

function solution(queue1, queue2) {
    let answer = -1;
    let N = queue1.length;
    let queue3 = queue1.concat(queue2);
    
    let sum1 = 0;
    let sum2 = 0;
    for(let i=0; i<N; i++) {
        sum1 += queue1[i];
        sum2 += queue2[i];
    }
    
    let sum = sum1+sum2;
    
    let pointer1 = 0;
    let pointer2 = N;
    
    let count = 0;
    while(count <= queue3.length*2) {
        if(sum1===sum/2) {
            return count;
        } else if(sum1<sum/2) {
            sum1 += queue3[pointer2++];
        } else {
            sum1 -= queue3[pointer1++];
        }
        count++;
    }

    return answer;
}

회고

queue를 합치는 것까지는 금방 떠올랐는데 sum1이 sum/2보다 작을 때 무조건 insert 되어야 하는 이유를 잘 모르겠어서 삽질을 한 것 같다...