.png)
문제 설명
카카오에서는 무료 셔틀버스를 운행하기 때문에 판교역에서 편하게 사무실로 올 수 있다. 카카오의 직원은 서로를 '크루'라고 부르는데, 아침마다 많은 크루들이 이 셔틀을 이용하여 출근한다.
이 문제에서는 편의를 위해 셔틀은 다음과 같은 규칙으로 운행한다고 가정하자.
- 셔틀은 09:00부터 총 n회 t분 간격으로 역에 도착하며, 하나의 셔틀에는 최대 m명의 승객이 탈 수 있다.
- 셔틀은 도착했을 때 도착한 순간에 대기열에 선 크루까지 포함해서 대기 순서대로 태우고 바로 출발한다. 예를 들어 09:00에 도착한 셔틀은 자리가 있다면 09:00에 줄을 선 크루도 탈 수 있다.
일찍 나와서 셔틀을 기다리는 것이 귀찮았던 콘은, 일주일간의 집요한 관찰 끝에 어떤 크루가 몇 시에 셔틀 대기열에 도착하는지 알아냈다. 콘이 셔틀을 타고 사무실로 갈 수 있는 도착 시각 중 제일 늦은 시각을 구하여라.
단, 콘은 게으르기 때문에 같은 시각에 도착한 크루 중 대기열에서 제일 뒤에 선다. 또한, 모든 크루는 잠을 자야 하므로 23:59에 집에 돌아간다. 따라서 어떤 크루도 다음날 셔틀을 타는 일은 없다.
입력 형식
셔틀 운행 횟수 n, 셔틀 운행 간격 t, 한 셔틀에 탈 수 있는 최대 크루 수 m, 크루가 대기열에 도착하는 시각을 모은 배열 timetable이 입력으로 주어진다.
- 0 ＜ n ≦ 10
- 0 ＜ t ≦ 60
- 0 ＜ m ≦ 45
- timetable은 최소 길이 1이고 최대 길이 2000인 배열로, 하루 동안 크루가 대기열에 도착하는 시각이 HH:MM 형식으로 이루어져 있다.
- 크루의 도착 시각 HH:MM은 00:01에서 23:59 사이이다.
출력 형식
콘이 무사히 셔틀을 타고 사무실로 갈 수 있는 제일 늦은 도착 시각을 출력한다. 도착 시각은 HH:MM 형식이며, 00:00에서 23:59 사이의 값이 될 수 있다.
입출력 예
접근법
우선 문제를 쉽게 접근할 수 있도록 timetable에 주어진 문자형태의
시간을 int 형태의 분으로 변경하는 작업을 진행한다.
결과 값을 정렬하면 대기열에 순서도 파악하기 쉬워진다.
current에 540을 준 이유는 첫 버스가 9:00시에 출발인데 만약
탑승 인원이 해당 시간에 꽉차 있다면 바로 출발하기 때문에 최소값이
9 * 60 = 540이다.
핵심 코드는 for 부터다 n은 운행 회수이며 m은 탑승 가능 인원이다
결국 timetable 안에 들어있는 크루 대기 시간들의 총 값이 n*m보다
작다면 가장 마지막 시간에 쉽게 탑승 가능하나 같거나 초과할 경우는
가장 마지막에 탑승 가능한 시간대 보다 1분 정도는 빨리 대기해야 가능하다
이건 현실에서와도 동일하다.
n*m의 결과 만큼 비교를 해야하기 때문에 이중 for문이 사용되었으며
콘의 실제 탑승 가능한 시간을 저장하는 변수로 candidate를 사용했다.
배차 간격마다 오는 버스에 탑승 가능한 최종 시간은 계속 변경 가능하기 때문에
비교값으로 사용되는 current에 배차 간격을 더해 다시 저장하여
비교를 이어나간다.
최종적으로 얻어진 분을 시간과 분으로 다시 분리하여 결과값을 반환하면
문제를 해결할 수 있다.
===========================================================
def solution(n : int, t : int, m : int, timetable) -> str:
answer = ''
timetable = [int(time[:2]) * 60 + int(time[3:])
for time in timetable]
timetable.sort()
current = 540
for _ in range(n):
for _ in range(m):
#대기가 있는 경우 1분 전 도착
if timetable and timetable[0] <= current:
candidate = timetable.pop(0) - 1
else:
candidate = current
current += t
# 시, 분으로 다시 변경
h, m = divmod(candidate, 60)
return str(h).zfill(2) + ':' + str(m).zfill(2)