문제 보기 · Level 2 · 2022 KAKAO TECH INTERNSHIP · 정답률 58% · 푼 사람 17,725명 (2026-09-30 기준)1
문제
길이가 같은 두 큐가 있다. 한 큐의 맨 앞 원소를 빼서 다른 큐의 끝에 넣는 것을 작업 1회로 센다. 두 큐의 원소 합을 같게 만드는 최소 작업 횟수를 돌려준다. 불가능하면 −1을 돌려준다.
- 큐 길이 1~300,000
- 원소 1~\(10^9\). 합이 32비트 정수 범위를 넘을 수 있다
풀이
막히면 한 단계씩 펼친다2.
필요한 개념
- 큐와 덱: 앞에서 빼고 끝에 넣는 큐의 움직임
- 투 포인터와 슬라이딩 윈도: 두 큐를 이어 붙이면 queue1은 줄 위의 “창”이 된다
- 나눗셈과 합동: 전체 합이 2로 나누어떨어지는지, 그리고 줄 끝을 지나면 처음으로 돌아가는 원형 번호(나머지)
1단계 · 작은 예로 손으로 풀기
queue1 = [3, 2, 7, 2], queue2 = [4, 6, 5, 1]. 전체 합 30, 목표는 각 15.
- queue1 합 14 < 15 → queue2에서 4를 빼 queue1에 넣는다: queue1 = [3, 2, 7, 2, 4] (18)
- 18 > 15 → queue1에서 3을 빼 queue2에 넣는다: queue1 = [2, 7, 2, 4] (15)
2번 만에 된다. 두 큐를 한 줄로 이어 [3, 2, 7, 2, 4, 6, 5, 1]로 보면, queue1은 늘 이 줄의 연속 구간이다. 앞에서 빼면 구간의 왼쪽 끝이, queue2에서 받으면 오른쪽 끝이 한 칸씩 앞으로 간다.
2단계 · 가장 단순한 방법과 그 속도
매번 두 가지 작업을 모두 해 보는 방법(모든 경우 탐색)은 작업 수가 늘수록 경우가 두 배씩 늘어 안 된다. 큐를 실제로 옮기며 합을 매번 sum으로 다시 구해도 한 번에 30만 번이라 안 된다.
3단계 · 핵심 아이디어
- 줄 위의 창: arr = queue1 + queue2로 잇고, queue1을 창 [i, j)로 본다. 처음엔 i = 0, j = n이다. queue1에서 빼면 i += 1, queue2에서 받으면 j += 1. 창의 합을 변수 하나로 들고 다닌다.
- 투 포인터: 창 합이 목표보다 크면 줄여야 하니 왼쪽 끝을 뺀다(i += 1). 작으면 늘려야 하니 오른쪽 끝을 넣는다(j += 1). 모든 원소가 양수라 “빼면 줄고 넣으면 는다”가 늘 맞는다. 그래서 목표 합을 처음 만나는 순간의 이동 횟수가 최소다.
- 원형: queue2가 비면 queue1에서 넘어온 원소를 다시 받는다. 그래서 번호를
j % (2n)처럼 줄 길이로 나눈 나머지로 읽는다. - 포기할 때: 전체 합이 홀수면 바로 −1. 그 밖에는 이동이 일정 횟수를 넘도록 못 찾으면 −1이다. 이 풀이는 3n번까지 본다. 3n이면 충분한 이유는 이렇다. 두 큐를 이어 붙인 길이 2n의 원형 줄에서 queue1은 늘 연속한 구간이고, 작업 한 번은 그 구간의 왼쪽 끝이나 오른쪽 끝을 한 칸 민다. 어떤 구간(또는 그 나머지)을 queue1로 만드는 최소 작업 수는 모든 구간에서 3n − 3번을 넘지 않는다(증명은 각주)2.
4단계 · 코드 흐름
- arr = queue1 + queue2, n = 큐 길이, 전체 합 total.
- total이 홀수면 −1.
- 목표 = total // 2, 창 합 s = queue1의 합, i = 0, j = n.
- 이동 횟수 0부터 3n까지:
- s == 목표면 이동 횟수를 돌려준다.
- s > 목표면 s에서 arr[i % 2n]을 빼고 i += 1.
- 아니면 s에 arr[j % 2n]을 더하고 j += 1.
- 못 찾으면 −1.
5단계 · 파이썬 코드
def solution(queue1, queue2):
arr = queue1 + queue2 # 두 큐를 이은 원형 줄
n = len(queue1)
total = sum(arr)
if total % 2:
return -1
target = total // 2
s = sum(queue1) # queue1 = 창 arr[i:j]의 합
i, j = 0, n
for count in range(3 * n + 1):
if s == target:
return count
if s > target: # queue1 → queue2
s -= arr[i % (2 * n)]
i += 1
else: # queue2 → queue1
s += arr[j % (2 * n)]
j += 1
return -1
- 큐를 실제로 옮기지 않는다. 두 번호 i, j와 합 s만 바꾸니 한 번에 \(O(1)\)이다.
- 파이썬 정수는 넘치지 않으니 합이 커도 괜찮다. C·자바는 64비트 정수(long)를 써야 한다.
6단계 · 실행 추적
queue1 = [1, 2, 1, 2], queue2 = [1, 10, 1, 2] → arr = [1, 2, 1, 2, 1, 10, 1, 2], 목표 10
| 이동 | 창 [i, j) | 합 s | 다음 |
|---|---|---|---|
| 0 | [0, 4) | 6 | 작다 → 1 받음 |
| 1 | [0, 5) | 7 | 작다 → 10 받음 |
| 2 | [0, 6) | 17 | 크다 → 1 뺌 |
| 3 | [1, 6) | 16 | 크다 → 2 뺌 |
| 4 | [2, 6) | 14 | 크다 → 1 뺌 |
| 5 | [3, 6) | 13 | 크다 → 2 뺌 |
| 6 | [4, 6) | 11 | 크다 → 1 뺌 |
| 7 | [5, 6) | 10 | 같다 |
답은 7이다. queue1 = [10], queue2 = [1, 2, 1, 2, 1, 2, 1]이 된다.
7단계 · 복잡도와 흔한 실수
이동을 많아야 3n번 하니 \(O(n)\)이다(처음 합 구하기 포함).
- 큐를
pop(0)으로 실제로 옮기고sum을 매번 다시 구해 \(O(n^2)\)이 된다. - 원형을 생각하지 않고 j가 줄 끝(2n)을 넘을 때 번호가 범위를 벗어난다.
- 끝나는 조건 없이 돌려 답이 −1인 입력에서 멈추지 않는다.
-
프로그래머스 스쿨, “두 큐 합 같게 만들기” (https://school.programmers.co.kr/learn/courses/30/lessons/118667), 2026-09-30 조회. ↩
-
상한의 증명: 처음 queue1은 구간 [0, n)이고, 왼쪽 끝을 a칸, 오른쪽 끝을 b칸 밀면 작업은 a + b번, 구간은 [a, n + b)다. 길이 k(1 ≤ k ≤ n), 시작 L인 목표 구간을 만들려면 a ≡ L (mod 2n), b = a + k − n ≥ 0이라 a ≥ n − k이고, 작업 수는 n − k + 2r이다(r = (L − n + k) mod 2n). 그 나머지 구간(길이 2n − k ≥ n, 시작 L + k, 합이 같다)을 queue1로 만들면 a ≡ L + k, b = a + n − k라 작업 수는 n − k + 2s다(s = (L + k) mod 2n). s − r ≡ n (mod 2n)이므로 r과 s 가운데 하나는 n − 1 이하다. 그래서 둘 중 작은 쪽은 n − k + 2(n − 1) = 3n − k − 2 ≤ 3n − 3을 넘지 않는다(k = 1에서 같아질 수 있다). 길이가 n보다 긴 목표는 그 나머지(길이 n 이하)로 같은 논증을 쓴다. 투 포인터가 최솟값을 찾는 증명: 최소 해를 (a, b)라 하자. 포인터는 늘 늘기만 하므로 언젠가 i = a나 j = b 중 하나에 먼저 닿는다. i = a에 먼저 닿았다면(j ≤ b) 창은 목표 구간의 부분이라 합이 목표 이하이고, 원소가 모두 양수라 목표에 닿을 때까지 j만 는다. j = b에 먼저 닿으면 반대로 i만 는다. 따라서 늦어도 a + b번째에 목표를 만나고, 처음 만난 순간의 작업 수는 a + b* 이하, 곧 최소다. 이 두 논증으로 3n번까지 보는 이 풀이는 모든 n에서 맞다. 실험(n ≤ 5의 모든 입력 128,953개와 n ≤ 8의 무작위 20,000개에서 BFS 최솟값과 일치)은 이 결론과 맞는다. ↩ ↩2