118667. 두 큐 합 같게 만들기

문제

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

제한사항

풀이

import java.util.*;

class Solution {
    public int solution(int[] queue1, int[] queue2) {
        Queue<Integer> q1 = new LinkedList<>();
        Queue<Integer> q2 = new LinkedList<>();
        long q1Sum = 0;
        long q2Sum = 0;
        int n = queue1.length;
        int job = 0;
        for(int i = 0; i< n;i++) {
            q1Sum+=queue1[i];
            q1.offer(queue1[i]);
        }
        
        for(int i = 0; i< n;i++) {
            q2Sum+=queue2[i];
            q2.offer(queue2[i]);
        }
        
        // 모든 큐의 요소 총합이 홀수이면 각 큐의 원소 합을 같게 만들 수 없다.
        if((q1Sum+q2Sum) % 2 == 1)
            return -1;
        
        while(job<=4 * n) {
            if(q1Sum == q2Sum)
                return job;
            
            if(q1Sum > q2Sum) {
                int head = q1.poll();
                q2.offer(head);
                q1Sum-=head;
                q2Sum+=head;
            }
            
            else {
                int head = q2.poll();
                q1.offer(head);
                q1Sum+=head;
                q2Sum-=head;
            }
            
            job++;
        }
        
        return -1;
    }
}

회고

큐를 생성해서 로직을 구현하는 것까지는 어려움이 없었다. 하지만 두 큐를 조작하면서 언제 비교를 더 이상하지 말아야 하는지 아는 게 핵심이었다. 

두 큐를 하나의 큐로 통합해서 볼 수 있다. 각 큐의 포인터가 큐의 요소 대소 관계를 따지며 이동할 것이다. 최악의 상황은 아무리 이동해도 두 큐의 요소의 합이 같은 경우가 없을 때이다. 그럴 경우 멈춰주고 -1을 반환해줘야 한다. 이동하다 보면 포인터가 다시 원상태로 돌아올 상황이 생길 것인데, 이때 멈춰줘야 한다. 이때까지 이동을 얼마나 할지 알아야 한다. 문제에서 -1을 반환하는 예시를 직접 시뮬레이션하면서 하니까 이해가 쉬웠다.

각 큐의 길이는 동일하다. 각 큐의 길이를 n이라고 하면, 기댓값이 나올 때까지 이동을 할 텐데 처음상태에서 이동하면 n 만큼 이동할 것이다.

위의 예시를 보면 이해가 수월하다. [1, 1]과 [1, 5]는 각 큐의 합이 2와 6이다. 큐의 합이 동일하도록 queue2에서 queue1으로 요소가 넘어갈 것이다. 이동하다 보면 [1, 1, 1, 5]와 []이 된다. 즉, n만큼 이동한다.

이제는 각 큐의 합이 9와 0이다. 다시 큐의 합이 동일할 때까지 queue1에서 queue2로 이동할 것이다.이동하다 보면 [], [1, 1, 1, 5]이 된다. 즉, 2n만큼 이동한다.

각 큐의 합이 0과 9이다. 또 이동이 반복된다. 계속 이렇게 큐의 합이 동일할 때까지 이동하다보면 무한히 이동할 것이다. 이동하다가 처음 상태로 돌아가면 더 이상 이동하지 않아도 될 것이다. 처음 상태로 돌아가는 이동이면 그 이후의 이동은 예상을 할 수 있기 때문이다. 다시 예시로 돌아가자. 마지막 이동이 [], [1, 1, 1, 5]였다. 여기서 이동이 발생할 것이고 [1, 1] [1, 5]가 될 때가 있다. 맞다. 다시 처음 상태로 되돌아왔다. 이동 거리는 n이다.

그래서 처음 상태로 돌아올 때까지 이동은 총 (n+2n+n) 만큼 했으므로 4 * n 만큼만 이동해 보면 된다. 그 이상의 이동은 무의미하다.