문제 요약
셔틀은 09:00부터 총 n회, t분 간격으로 도착한다. 한 셔틀에는 최대 m명의 크루가 탑승할 수 있다.
크루는 도착 시각 순서대로 탑승하며, 콘은 같은 시각에 도착한 다른 크루보다 항상 뒤에 선다.
콘이 마지막 셔틀까지 포함해 무사히 탑승할 수 있는 가장 늦은 도착 시각을 구해야 한다.
핵심 아이디어
콘이 탑승할 수 있는 가장 늦은 시각은 마지막 셔틀의 탑승 결과만 보면 알 수 있다.
- 마지막 셔틀에 빈자리가 있다면 콘은 마지막 셔틀 도착 시각에 도착하면 된다.
- 마지막 셔틀이 정원
m명으로 가득 찼다면, 마지막으로 탑승한 크루보다 1분 먼저 도착해야 한다.
콘은 같은 시각에 도착한 크루 중 가장 뒤에 서므로, 마지막으로 탄 크루와 같은 시각에 도착하면 탑승하지 못한다.
따라서 모든 셔틀에 기존 크루를 먼저 태우는 과정을 시뮬레이션한 뒤 마지막 셔틀의 탑승 인원과 마지막 탑승 시각을 확인한다.
시간을 분 단위 정수로 변환하기
문자열 시각을 비교하거나 분 단위 덧셈을 직접 처리하면 복잡해질 수 있다. 모든 시각을 자정부터 지난 분으로 변환하면 간단하게 계산할 수 있다.
def to_minutes(time_text):
hour, minute = map(int, time_text.split(":"))
return hour * 60 + minute반환할 때는 다시 HH:MM 형식으로 변환한다.
def to_time(minutes):
return f"{minutes // 60:02d}:{minutes % 60:02d}"셔틀 탑승 시뮬레이션
크루 도착 시각을 오름차순으로 정렬하고, 아직 탑승하지 않은 첫 번째 크루를 가리키는 포인터 index를 사용한다.
각 셔틀에서 다음 조건을 만족하는 크루를 최대 m명까지 태운다.
크루 도착 시각 <= 셔틀 도착 시각셔틀은 도착한 순간에 줄을 선 크루도 태우므로 비교 연산자는 <가 아니라 <=다.
Python 코드
def solution(n, t, m, timetable):
def to_minutes(time_text):
hour, minute = map(int, time_text.split(":"))
return hour * 60 + minute
def to_time(minutes):
return f"{minutes // 60:02d}:{minutes % 60:02d}"
crew_times = sorted(to_minutes(time) for time in timetable)
index = 0
last_shuttle_time = 9 * 60 + (n - 1) * t
for shuttle_index in range(n):
shuttle_time = 9 * 60 + shuttle_index * t
boarded = 0
last_boarded_time = -1
while (
index < len(crew_times)
and boarded < m
and crew_times[index] <= shuttle_time
):
last_boarded_time = crew_times[index]
index += 1
boarded += 1
# 마지막 셔틀의 탑승 결과로 콘의 도착 시각을 결정한다.
if shuttle_time == last_shuttle_time:
if boarded < m:
return to_time(shuttle_time)
return to_time(last_boarded_time - 1)코드 설명
크루 도착 시각 정렬
crew_times = sorted(to_minutes(time) for time in timetable)대기열은 도착 순서대로 구성되므로 먼저 도착 시각을 정렬한다.
현재 셔틀에 탑승할 크루 처리
while (
index < len(crew_times)
and boarded < m
and crew_times[index] <= shuttle_time
):아직 탑승하지 않은 크루가 있고, 셔틀에 자리가 있으며, 해당 크루가 셔틀 도착 시각 이전 또는 같은 시각에 도착했다면 탑승시킨다.
탑승시킬 때마다 index를 증가시키므로 각 크루는 한 번만 확인한다.
마지막 셔틀에 자리가 있는 경우
if boarded < m:
return to_time(shuttle_time)마지막 셔틀이 가득 차지 않았다면 콘은 셔틀이 도착하는 시각에 대기열에 도착해도 탑승할 수 있다.
마지막 셔틀이 가득 찬 경우
return to_time(last_boarded_time - 1)마지막으로 탄 크루와 같은 시각에 도착하면 콘은 그 크루보다 뒤에 서게 된다.
따라서 콘은 마지막 탑승 크루보다 정확히 1분 먼저 도착해야 한다.
정확성
각 셔틀에 대해 알고리즘은 도착 시각이 셔틀 도착 시각 이하인 크루를 도착 순서대로 최대 m명까지 탑승시킨다. 이는 문제의 대기 순서와 탑승 규칙을 그대로 따른다.
마지막 셔틀 이전의 탑승 결과는 마지막 셔틀 대기열을 결정하므로 모든 셔틀을 순서대로 시뮬레이션해야 한다.
마지막 셔틀에 빈자리가 있으면 콘은 셔틀 도착 시각에 도착해도 탑승할 수 있으며, 이보다 늦게 도착하면 셔틀이 출발하므로 더 늦은 시각은 불가능하다.
마지막 셔틀이 가득 찬 경우, 콘은 마지막 탑승 크루보다 먼저 도착해야 한다. 분 단위 시각에서 가능한 가장 늦은 시각은 마지막 탑승 시각 - 1분이다.
따라서 알고리즘이 반환하는 시각은 콘이 탑승할 수 있는 가장 늦은 도착 시각이다.
시간 복잡도
크루 수를 C라고 하자.
크루 도착 시각 정렬에 O(C log C)가 필요하다. 이후 각 크루는 최대 한 번만 탑승 처리되므로 시뮬레이션은 O(C + n)이다.
O(C log C)공간 복잡도
분 단위로 변환한 크루 도착 시각 배열을 저장한다.
O(C)주의할 점
- 셔틀 도착 시각과 같은 시각에 도착한 크루도 탑승 가능하므로
<=를 사용한다. - 콘은 같은 시각에 도착한 크루보다 뒤에 서므로 마지막 셔틀이 가득 차면
-1분이 필요하다. - 마지막 셔틀만 확인하면 안 된다. 이전 셔틀이 어떤 크루를 태웠는지에 따라 마지막 셔틀 대기열이 달라진다.
last_boarded_time - 1은00:00이 될 수 있으므로 시각 변환은 0시도 처리해야 한다.- 크루 수가 많아도 각 크루를 한 번만 처리하는 포인터 방식으로 구현해야 한다.
정리
이 문제는 시간 문자열을 분 단위 정수로 변환하고, 셔틀 도착 순서대로 기존 크루를 태우는 시뮬레이션 문제다.
마지막 셔틀의 빈자리 여부에 따라 셔틀 도착 시각 또는 마지막 탑승 크루보다 1분 이른 시각을 반환하면 된다.
