문제 보기 · Level 3 · 2018 KAKAO BLIND RECRUITMENT (1차) · 정답률 46% · 푼 사람 8,890명 (2026-09-30 기준)1
문제
셔틀이 09:00부터 t분 간격으로 n번 오고, 한 번에 최대 m명을 태운다. 셔틀은 도착한 순간까지 줄 선 사람을 순서대로 태운다. 크루들이 줄에 서는 시각이 주어진다. 콘이 셔틀을 탈 수 있는 가장 늦은 도착 시각을 "HH:MM"으로 돌려준다. 콘은 같은 시각에 온 사람 중 맨 뒤에 선다.
- 0 < n ≤ 10, 0 < t ≤ 60, 0 < m ≤ 45
- 크루 최대 2,000명, 도착 시각 00:01~23:59
풀이
막히면 한 단계씩 펼친다.
1단계 · 작은 예로 손으로 풀기
버스 2대(09:00, 09:10), 한 대에 2명, 크루 [09:00, 09:05, 09:05]
- 09:00 버스: 09:00 크루 1명 탑승(자리 1개 남음)
- 09:10 버스(마지막): 09:05 크루 2명 탑승 → 가득 참
콘은 마지막 버스를 타야 가장 늦게 올 수 있다. 그런데 마지막 버스가 가득 찼으니, 마지막에 탄 사람(09:05)보다 1분 먼저 와야 그 사람 앞에 선다. 답은 “09:04”다. 마지막 버스에 자리가 남았다면 버스가 오는 시각에 맞춰 오면 된다.
2단계 · 가장 단순한 방법과 그 속도
콘의 도착 시각 후보(00:00~23:59, 1,440개)를 늦은 것부터 하나씩 넣어 보고, 탈 수 있는 첫 시각을 고르는 방법도 된다. 후보마다 크루 2,000명을 시뮬레이션하면 약 300만 번이다.
하지만 1단계에서 본 것처럼 답은 두 경우뿐이라, 시뮬레이션 한 번이면 된다.
3단계 · 핵심 아이디어
- 크루를 분 단위로 바꿔 정렬하고, 버스를 차례로 보내며 “버스 시각 이하에 온 사람”을 앞에서부터 m명까지 태운다.
- 마지막 버스만 보면 된다. 콘은 늦게 올수록 좋고, 마지막 버스보다 늦으면 못 탄다.
- 마지막 버스에 자리가 남았다 → 마지막 버스 시각에 온다.
- 가득 찼다 → 마지막에 탄 사람보다 1분 먼저 온다. 그러면 그 사람을 밀어내고 탄다.
4단계 · 코드 흐름
- 크루 시각을 분으로 바꿔 정렬한다.
- 버스 i = 0 … n − 1마다 시각 540 + i × t에, 줄 앞에서부터 그 시각 이하인 사람을 m명까지 태운다.
- 마지막 버스의 탑승자가 m명 미만이면 마지막 버스 시각, 아니면 마지막 탑승자 시각 − 1.
"HH:MM"으로 바꿔 돌려준다.
5단계 · 파이썬 코드
def solution(n, t, m, timetable):
crew = sorted(int(x[:2]) * 60 + int(x[3:]) for x in timetable)
idx = 0
for i in range(n):
bus = 540 + i * t # 09:00 = 540분
riders = []
while len(riders) < m and idx < len(crew) and crew[idx] <= bus:
riders.append(crew[idx])
idx += 1
# 반복이 끝나면 bus와 riders에는 마지막 버스의 값이 남아 있다
ans = bus if len(riders) < m else riders[-1] - 1
return f"{ans // 60:02d}:{ans % 60:02d}"
int(x[:2]) * 60 + int(x[3:]): “08:59”를 539분으로 바꾼다.idx: 아직 안 탄 크루 중 맨 앞의 번호다. 버스가 바뀌어도 이어서 쓴다.- 반복문이 끝나도 반복문 안에서 만든 변수
bus,riders가 남아 있다(파이썬은 그렇다). n ≥ 1이라 늘 한 번은 만들어진다.
6단계 · 실행 추적
n = 2, t = 1, m = 2, 크루 [09:00, 09:00, 09:00, 09:00]
| 버스 | 시각 | 탄 사람 | 남은 크루 |
|---|---|---|---|
| 1 | 09:00 | 09:00, 09:00 | 2명 |
| 2 (마지막) | 09:01 | 09:00, 09:00 | 0명 |
마지막 버스가 가득 찼으니 09:00 − 1분 = “08:59”다.
7단계 · 복잡도와 흔한 실수
정렬 \(O(k \log k)\)(k는 크루 수)와 한 번 훑기라 빠르다.
- 마지막 버스가 가득 찼을 때 “마지막 탑승자 − 1분” 대신 “첫 버스 시각”이나 “마지막 버스 시각”을 돌려준다.
- 같은 시각에 온 크루보다 콘이 뒤에 선다는 규칙을 놓쳐, 마지막 탑승자와 같은 시각에 와도 탈 수 있다고 본다.
- 버스가 도착한 바로 그 순간에 줄을 선 사람도 탈 수 있다. 조건을
crew[idx] < bus로 쓰면 그 사람을 빼먹는다.
-
프로그래머스 스쿨, “[1차] 셔틀버스” (https://school.programmers.co.kr/learn/courses/30/lessons/17678), 2026-09-30 조회. ↩