문제 보기 · Level 4 · 2019 KAKAO BLIND RECRUITMENT · 정답률 35% · 푼 사람 7,323명 (2026-09-30 기준)1
문제
회전판에 음식 N개가 있고, 음식마다 다 먹는 데 걸리는 시간이 있다. 1번부터 번호 순으로 음식 하나를 1초씩 먹고 다음 음식으로 넘어가며, 다 먹은 음식은 건너뛴다. 마지막 음식 다음에는 다시 1번이 온다. K초 뒤 방송이 끊겼을 때, 다시 시작하면 먹을 음식 번호를 돌려준다. 더 먹을 음식이 없으면 −1을 돌려준다.
- 정확성: 음식 최대 2,000개, 시간 최대 1,000, K 최대 2,000,000
- 효율성: 음식 최대 200,000개, 시간 최대 10⁸, K 최대 2 × 10¹³
풀이
막히면 한 단계씩 펼친다.
필요한 개념
정렬과 정렬 기준: 음식을 “빨리 끝나는 순서”로 정렬하면, 한 바퀴씩 도는 시간을 음식 하나가 끝날 때까지 한꺼번에 뺄 수 있다.
1단계 · 작은 예로 손으로 풀기
음식 [3, 1, 2], K = 5
| 초 | 먹는 음식 | 남은 시간 |
|---|---|---|
| 0~1 | 1번 | [2, 1, 2] |
| 1~2 | 2번 | [2, 0, 2] |
| 2~3 | 3번 | [2, 0, 1] |
| 3~4 | 1번 | [1, 0, 1] |
| 4~5 | 3번(2번은 다 먹음) | [1, 0, 0] |
5초에 끊겼고 다음은 1번이다. 한 바퀴를 돌 때마다 남은 음식이 모두 1씩 준다는 것이 보인다.
2단계 · 가장 단순한 방법과 그 속도
1초씩 흉내 내면 K번 돈다. K가 2 × 10¹³이면 어림없다. 정확성 테스트(K ≤ 200만)는 통과해도 효율성은 못 넘는다.
3단계 · 핵심 아이디어
- 한 바퀴 = 남은 음식 수만큼의 초: 음식이 m개 남았으면 한 바퀴에 m초가 걸리고, 모든 음식이 1씩 준다.
- 가장 빨리 끝나는 음식까지 한꺼번에: 남은 음식 중 가장 적게 남은 음식이 t초 남았다면, t바퀴 동안은 음식 수가 그대로 m개다. 그 t바퀴(t × m초)를 한 번에 뺀다. 그러면 그 음식이 끝나고 m − 1개가 남는다.
- 정렬로 차례 정하기: 음식을 시간 순으로 정렬해 두면 “다음에 끝날 음식”을 차례로 볼 수 있다. 앞 음식까지 이미 뺀 바퀴 수를 prev라 하면, 다음 음식까지는 (t − prev) × m초다.
- 남는 초가 다음 음식까지의 시간보다 적으면: 그때 남은 음식을 번호 순으로 세우고 (남은 K) % m 번째가 답이다. 남은 K는 한 바퀴(m초)보다 클 수 있다. 나눗셈 정리로 K = q × m + r(0 ≤ r < m)로 나누면, q는 다 같이 도는 바퀴 수이고 r = K % m은 그 뒤에 지나가는 음식 수다. K < (t − prev) × m이라 q는 t − prev보다 작다. 남은 음식은 모두 t − prev초 이상 남아 있으니, 그 q바퀴 동안 다 먹는 음식은 없다.
- 모든 음식의 시간 합이 K 이하면 더 먹을 게 없어 −1이다.
4단계 · 코드 흐름
- 시간 합 ≤ K면 −1.
- (시간, 번호)를 시간 순으로 정렬한다. prev = 0.
- 정렬된 순서로 음식을 보며: 남은 음식 수 m, 이번 층의 시간 layer = (t − prev) × m.
- K < layer면 남은 음식을 번호 순으로 정렬해 K % m 번째 번호를 돌려준다.
- 아니면 K −= layer, prev = t.
5단계 · 파이썬 코드
def solution(food_times, k):
if sum(food_times) <= k:
return -1
foods = sorted((t, i + 1) for i, t in enumerate(food_times)) # 빨리 끝나는 음식부터
n, prev = len(foods), 0
for idx, (t, _) in enumerate(foods):
m = n - idx # 아직 남은 음식 수
layer = (t - prev) * m # 이 음식이 끝날 때까지 도는 시간
if k < layer:
rest = sorted(i for _, i in foods[idx:])
return rest[k % m]
k -= layer
prev = t
return -1
sorted((t, i + 1) for ...): (시간, 번호) 튜플을 만들어 시간 순, 같으면 번호 순으로 정렬한다.- 같은 시간의 음식이 여럿이면 둘째 음식의 layer는 (t − t) × m = 0이라 그냥 지나간다.
foods[idx:]: 아직 안 끝난 음식들이다. 번호 순으로 다시 정렬해 회전판 순서를 되찾는다.
6단계 · 실행 추적
음식 [4, 2, 3, 6, 7, 1, 5, 8], K = 16
| 다음에 끝날 음식(번호, 시간) | 남은 음식 수 m | 이번 층 시간 | 층을 빼기 전 K |
|---|---|---|---|
| 6번, 1 | 8 | (1 − 0) × 8 = 8 | 16 → 8 |
| 2번, 2 | 7 | (2 − 1) × 7 = 7 | 8 → 1 |
| 3번, 3 | 6 | (3 − 2) × 6 = 6 | 1 < 6, 멈춤 |
남은 음식은 번호 순으로 [1, 3, 4, 5, 7, 8]이고, 1 % 6 = 1이라 두 번째인 3번이 답이다.
7단계 · 복잡도와 흔한 실수
정렬 \(O(N \log N)\)이 전부다. 음식 20만 개로 재 보니 0.2초 안팎이었다.
- 1초씩 흉내 내 효율성에서 시간 초과가 난다.
- 남은 음식을 번호 순으로 다시 정렬하지 않고 시간 순서 그대로 K % m 번째를 고른다.
- 시간 합이 정확히 K인 경우(모두 다 먹음)를 −1로 처리하지 않는다.
-
프로그래머스 스쿨, “무지의 먹방 라이브” (https://school.programmers.co.kr/learn/courses/30/lessons/42891), 2026-09-30 조회. ↩