두 큐 합 같게 만들기

문제

길이가 같은 두 개의 큐가 주어집니다. 하나의 큐에서 원소를 추출(pop)하여 다른 큐에 집어넣는(insert) 작업을 통해 두 큐의 원소 합이 같도록 만들려고 합니다. 이때 필요한 작업의 최소 횟수를 구하는 프로그램을 작성하는 문제입니다. 한 번의 pop과 한 번의 insert를 합쳐서 작업 횟수를 1회로 간주합니다. 만약 어떤 방법으로도 두 큐의 원소 합을 같게 만들 수 없다면 -1을 반환해야 합니다.

• 입력: 정수 배열 queue1, queue2 (각 배열의 길이는 1 이상 300,000 이하, 원소는 10^9 이하의 자연수)
• 출력: 두 큐의 합을 같게 만들기 위해 필요한 최소 작업 횟수 (불가능할 경우 -1)

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

풀이: 큐(Queue)와 탐욕법(Greedy)을 이용한 합산 조정

두 큐의 합을 비교하여, 합이 더 큰 큐에서 원소를 빼서 합이 더 작은 큐로 옮기는 과정을 반복하는 직관적인 탐욕법 풀이입니다. 모든 원소가 양수이므로 이 방식은 항상 두 큐의 합을 평균에 가깝게 만들어줍니다.

• 자료형 오버플로우 대비: 각 큐의 원소가 최대 10^9이고 길이가 300,000이므로, 모든 원소의 합은 int형의 최댓값(약 21억)을 아득히 초과할 수 있습니다. 따라서 두 큐의 합(sum1, sum2)을 담는 변수를 long 타입으로 선언하여 오버플로우를 완벽하게 방지합니다.
• 큐 초기화: 배열로 주어진 두 큐의 데이터를 자바의 Queue<Integer>(LinkedList)에 각각 담고, 동시에 초기 합계를 계산합니다.
• 합산 조정 (Greedy): sum1과 sum2가 같아질 때까지 반복문을 수행합니다.
  • sum1 > sum2: 1번 큐의 합이 더 크므로, 1번 큐에서 원소를 뽑아(poll) 2번 큐에 넣습니다(add). 그리고 각 큐의 합을 갱신합니다.
  • sum1 < sum2: 2번 큐의 합이 더 크므로, 반대로 2번 큐에서 원소를 뽑아 1번 큐에 넣고 합을 갱신합니다.

종료 조건(최댓값) 설계의 수학적 원리

무한 루프를 방지하기 위해 최대 작업 횟수를 어떻게 설정해야 할까요? 두 큐를 이어 붙인 길이가 2N인 하나의 긴 배열을 상상해 보면 답을 알 수 있습니다.

큐 간의 원소 이동은 이 긴 배열 위에서 구간의 시작점(Start)과 끝점(End)이 한 칸씩 오른쪽으로 이동하는 투 포인터(Two Pointers)의 원리와 완벽히 일치합니다.

• 시작점 포인터가 전체를 한 바퀴 도는 데 최대 2N번의 연산이 필요합니다.
• 끝점 포인터가 전체를 한 바퀴 도는 데 최대 2N번의 연산이 필요합니다.
• 즉, 시작점과 끝점이 모든 경우의 수(부분 배열)를 탐색하며 완전히 제자리로 돌아오기까지 최대 2N + 2N = 4N번의 연산이 발생합니다.

따라서 큐 1개의 길이를 N이라고 할 때, 최대 작업 횟수 한계점(Limit)을 4N으로 설정하면 모든 엣지 케이스를 안전하게 포함하면서 무한 루프를 완벽하게 방어할 수 있습니다.

코드

import java.util.*;

class Solution {
    public int solution(int[] queue1, int[] queue2) {
        int ans = 0;
        long sum1 = 0;
        long sum2 = 0;
        
        Queue<Integer> q1 = new LinkedList<>();
        Queue<Integer> q2 = new LinkedList<>();
        
        for (int i : queue1) {
            sum1 += i;
            q1.add(i);
        }
        
        for (int i : queue2) {
            sum2 += i;
            q2.add(i);
        }
        
        // 큐 1개 길이의 4배(4N)를 최대 탐색 한계치로 설정
        int limit = queue1.length * 4;
        
        while(sum1 != sum2) {
            // 한계치를 초과하면 어떤 방법으로도 같게 만들 수 없음을 의미
            if (ans > limit) {
                break;
            }
            
            if (sum1 > sum2) {
                int x = q1.poll();
                sum1 -= x;
                sum2 += x;
                q2.add(x);
            } else if (sum1 < sum2) {
                int x = q2.poll();
                sum2 -= x;
                sum1 += x;
                q1.add(x);
            }
            ans++;
        }
        
        if (sum1 != sum2) {
            ans = -1;
        }
        
        return ans;
    }
}

알고리즘 분류

그리디 알고리즘 (Greedy), 큐 (Queue)