본문으로 건너뛰기

118667 - 두 큐 합 같게 만들기

info

풀이 키워드​

스포주의

큐


풀이 코드​

info
  • 메모리: 150000 KB
  • 시간: 49 ms
import java.util.*;

class Solution {
    public int solution(int[] queue1, int[] queue2) {
        int maxTrial = queue1.length * 3;
        Deque<Integer> q1 = new ArrayDeque<>();
        Deque<Integer> q2 = new ArrayDeque<>();
        
        long s1 = 0;
        long s2 = 0;
        for (int i : queue1) {
            q1.add(i);
            s1 += i;
        }
        for (int i : queue2) {
            q2.add(i);
            s2 += i;
        }
        
        long total = s1 + s2;
        if ((total & 1) == 1) return -1;
        long half = total >> 1;
        
        for (int t = 0; t < maxTrial; ++t) {
            if (s1 < s2) {
                int k = q2.poll();
                q1.add(k);
                s1 += k;
                s2 -= k;
            }
            else if (s2 < s1) {
                int k = q1.poll();
                q2.add(k);
                s2 += k;
                s1 -= k;
            }
            else {
                return t;
            }
        }
        
        return -1;
    }
}

풀이 해설​

💥 틀리기 쉬운 반례​

1번에서 WA를 받았다면 다음의 반례를 의심해보면 된다.

[1, 1, 1, 1], [1, 1, 7, 1]
답: 9

maxTrial을 queue1.length * 2로 설정했을 때 1번만 틀렸었는데

이는 큐 길이의 2배 정도면 다 판정될거라고 잘못 생각했던 탓이다.

큐 길이를 n이라고 했을 때, (즉, s1 + s2 = 2n)

반례에서 필요한 연산 수는

  1. [1, 1, 1, 1, 1, 1, 7], [1]: [q1 ⬅️ q2] : n - 1 번
  2. [7], [1, 1, 1, 1, 1, 1, 1]: [q1 ➡️ q2] : n + (n-2) 번

총 3n - 3 번이다.

7과 다른 큐에 놓여야 하는 원소가 7 뒤에 딱 1개 있는 것이 1번 작업에서 n-1 번 연산을 하게 되는 최악의 경우이다.

7 뒤에 2개가 있었다면 n-2번 연산이므로 덜 최악이고,

7이 맨 뒤에 있었다면 7 앞의 녀석들만 q1으로 옮겨주고 2번 작업 없이 끝나기 때문이다.


따라서 풀이 코드의 maxTrial을 queue1.length * 3 - 3 으로 설정하면 WA 였다가

queue1.length * 3 - 2로 1 늘리면 AC가 된다.

실전에선 바쁘니, queue1.length * 2로 막히면 queue1.length * 3을 시도해보는 것이 최선인 것 같다.

어차피 큐 길이가 ≤300,000\le 300,000라서 T(3n)T(3n)이라 해봤자 10610^6 iteration이 안된다.


메모​

  • 요즘같으면 문제에 큐라는거 언급 안하고 오버플로우 주의도 안써줬을듯
  • 최대 시도 횟수 계산만 주의하면 크게 어려운 부분은 없는 것 같다.