[프로그래머스] 두 큐 합 같게 만들기 (Java) — 그리디

📌 핵심 요약

• 문제 핵심 — 두 큐 사이에서 원소를 옮겨 두 큐의 합을 같게 만드는 최소 이동 횟수를 구함
• 핵심 아이디어 — 매번 합이 큰 쪽에서 빼서 작은 쪽으로 이동하면 자연스럽게 균형으로 수렴 (그리디)
• 오버플로 주의 — 원소 합이 커질 수 있으므로 합은 long 으로 관리
• 무한 루프 차단 — 답이 없을 수도 있으니 최대 이동 횟수 제한을 두고 초과하면 -1

 

목차

1 문제 소개

길이가 같은 두 큐 queue1, queue2 가 주어집니다.

한 번의 작업은 한 큐의 맨 앞 원소를 빼서 다른 큐의 맨 뒤에 넣는 것입니다.

이 작업을 반복해 두 큐의 원소 합을 같게 만들 때, 필요한 최소 작업 횟수를 구합니다.

어떻게 해도 같게 만들 수 없으면 -1 을 반환합니다.

Programmers Lv.2

두 큐 합 같게 만들기

큐 길이 1 ~ 300,000 · 원소 1 ~ 10⁹

분류: 투 포인터 / 큐

제약 조건

• 두 큐의 길이는 같고, 각각 1 이상 300,000 이하.
• 원소는 1 이상 10⁹ 이하의 자연수.

2 접근 방법

합이 큰 쪽에서 작은 쪽으로

두 큐의 합을 같게 만들려면, 결국 합이 큰 큐가 원소를 내주고 작은 큐가 받아야 합니다.

그래서 매 단계마다 sum1 과 sum2 를 비교해서, 더 큰 쪽의 맨 앞 원소를 빼서 작은 쪽으로 옮깁니다.

이렇게 하면 두 합의 차이가 점점 줄어들며 균형점으로 수렴합니다. 굳이 모든 경우를 시도하지 않아도 되는 그리디 방식입니다.

ℹ️

왜 -1 인 경우가 생기나?

두 큐 전체 합이 홀수면 반으로 똑같이 나눌 수 없습니다. 이 경우는 시작하기도 전에 바로 -1 입니다. 그 외에도 아무리 옮겨도 같아지지 않는 경우가 있어, 이동 횟수 상한으로 무한 루프를 막아야 합니다.

두 가지 함정 — long과 무한루프

• 오버플로 — 원소가 최대 10⁹, 개수가 최대 30만 개라 합이 int 범위를 훌쩍 넘습니다. 합은 반드시 long 으로 둡니다.
• 무한 루프 — 답이 없을 때 while 이 끝나지 않습니다. "큐 길이 × 4" 정도를 상한으로 두고, 넘어가면 -1 로 종료합니다.

3 풀이 코드

전체 코드

 

Java — Solution.java

import java.util.*;

class Solution {
    public int solution(int[] queue1, int[] queue2) {
        int answer = 0;
        Queue<Integer> q1 = new LinkedList<>();
        Queue<Integer> q2 = new LinkedList<>();

        // 큐에 담으면서 각 큐의 합을 long으로 누적
        long sum1 = 0;
        for (int num : queue1) { q1.offer(num); sum1 += num; }

        long sum2 = 0;
        for (int num : queue2) { q2.offer(num); sum2 += num; }

        long total = sum1 + sum2;

        // 1. 총합이 홀수면 반으로 나눌 수 없으므로 -1
        if (total % 2 != 0) return -1;

        // 2. 무한 루프 방지용 최대 이동 횟수 (큐 길이의 약 4배)
        int maxLimit = queue1.length * 4;

        while (sum1 != sum2) {
            if (answer > maxLimit) return -1;
            if (q1.isEmpty() || q2.isEmpty()) return -1;

            // 3. 합이 큰 쪽에서 빼서 작은 쪽으로 이동
            if (sum1 > sum2) {
                int num = q1.poll();
                sum1 -= num; sum2 += num;
                q2.offer(num);
            } else {
                int num = q2.poll();
                sum2 -= num; sum1 += num;
                q1.offer(num);
            }

            answer++;
        }
        return answer;
    }
}

동작 흐름

흐름

while 한 바퀴가 하는 일

1. 두 합이 같아지면 반복을 멈추고 지금까지의 이동 횟수를 반환
2. 이동 횟수가 상한을 넘으면 → 답이 없는 경우이므로 -1
3. sum1 > sum2 면 q1의 맨 앞을 빼서 q2로, 반대면 q2 → q1
4. 옮긴 값만큼 두 합을 갱신하고 answer++ 후 다시 비교

4 핵심 포인트 정리

🚨

int로 합을 더하면 틀린다

원소 최대 10⁹, 개수 최대 30만 → 합이 최대 약 3 × 10¹⁴ 까지 갑니다. int(약 21억) 범위를 한참 넘으므로 반드시 long 을 써야 합니다. 메모리에 남겨둔 "int vs long 혼용" 실수가 정확히 이 지점입니다.

💡

매번 합을 다시 계산하지 않기

옮길 때마다 큐 전체를 더하면 O(n) 이 반복돼 느려집니다. 대신 옮긴 원소 값만큼 sum1, sum2 를 증분 갱신하면 한 번의 이동이 O(1) 이 됩니다.

⚠️

상한은 왜 "길이 × 4" 인가

두 큐를 한 줄로 이어 붙였다고 보면, 정답이 존재할 때 필요한 이동은 넉넉히 잡아도 전체 원소 수(2n)의 두 배 정도면 충분합니다. 큐 길이가 n 이므로 n × 4 = 2 × (2n) 가 안전한 상한이 됩니다. 이 선을 넘으면 답이 없는 경우로 판단합니다.

시간 복잡도

구분	내용	복잡도
한 번의 이동	poll / offer / 합 갱신 모두 상수 시간	O(1)
전체	이동 횟수가 상한(약 4n)으로 제한됨	O(n)
최대 입력	n = 300,000 기준 충분히 통과	통과

ℹ️

마무리

"큰 쪽이 작은 쪽에 넘겨준다"는 한 문장이 풀이의 전부입니다. 여기에 long으로 오버플로 방지 + 이동 횟수 상한으로 무한루프 차단 두 가지만 챙기면 깔끔하게 통과하는 문제입니다.

잘못된 내용이 있다면 지적부탁드립니다. 방문해주셔서 감사합니다.