문제
카카오에서는 무료 셔틀버스를 운행하기 때문에 판교역에서 편하게 사무실로 올 수 있다. 카카오의 직원은 서로를 '크루'라고 부르는데, 아침마다 많은 크루들이 이 셔틀을 이용하여 출근한다.
이 문제에서는 편의를 위해 셔틀은 다음과 같은 규칙으로 운행한다고 가정하자.
•
셔틀은 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사이의 값이 될 수 있다.
예시
정답
# 분 기준으로 변환
def str_to_time(str_list):
time_list = []
for t in str_list:
h, m = t.split(':')
time = int(h)*60 + int(m)
time_list.append(time)
return time_list
# time 형식으로 변환
def time_to_str(time):
hour = str(time // 60)
minute = str(time % 60)
if len(hour) < 2:
hour = '0' + hour
if len(minute) < 2:
minute = '0' + minute
return hour + ':' + minute
def solution(n, t, m, timetable):
# 버스 도착 시간
bus_list = [540]
for i in range(n-1):
bus_list.append(bus_list[-1]+t)
# 분 기준으로 크루 인원들 도착 시간 변경
timetable = str_to_time(timetable)
timetable = sorted(timetable) # 정렬 필요
# 각 버스에 탄 크루들의 탑승 시각 리스트
take_list = [None]*len(bus_list)
c = 0
for b in range(len(bus_list)):
r = 0
temp = []
# 정원이 다 차지 않았거나, 검색 범위 내인 경우 확인
while (r < m) & (c < len(timetable)):
if timetable[c] <= bus_list[b]: # 버스 도착 시간보다 일찍 도착한 경우
temp.append(timetable[c]) # 탑승 시킴
r += 1 # 정원 +1
c += 1 # 검색 범위 이동
else:
break
take_list[b] = temp # 탑승 리스트 업데이트
last_bus = len(bus_list)-1 # 맨 마지막 버스
if len(take_list[last_bus]) < m: # 정원이 다 차지 않은 경우
return time_to_str(bus_list[last_bus]) # 맨 마지막 버스 도착 시간에 탑승하면 된다.
else:
return time_to_str(take_list[last_bus][-1]-1) # 맨 마지막 버스에서 가장 늦게 탑승한 인원보다 1분 일찍 오면 된다.
Python
복사
풀이
•
가장 늦게 타기 위해서는 맨 마지막 버스에 정원이 다 차지 않았으면 맨 마지막 버스 도착 시간에, 만약에 정원이 다 찼으면 맨 마지막 버스에 가장 늦게 탑승한 크루의 탑승 시각보다 1분 더 빨리 오면 된다.
•
우선 분 기준으로 변환하여 대소를 비교하는 것이 좋으므로 분을 기준으로 변환하는 함수를 작성하였다.
# 분 기준으로 변환
def str_to_time(str_list):
time_list = []
for t in str_list:
h, m = t.split(':')
time = int(h)*60 + int(m)
time_list.append(time)
return time_list
Python
복사
•
그 다음 나중에 출력은 time의 형식이어야 하므로 time 형식으로 변환하는 함수를 작성하였다.
# time 형식으로 변환
def time_to_str(time):
hour = str(time // 60)
minute = str(time % 60)
if len(hour) < 2:
hour = '0' + hour
if len(minute) < 2:
minute = '0' + minute
return hour + ':' + minute
Python
복사
•
분을 기준으로 각 버스가 도착하는 시간을 리스트로 만들었다.
# 버스 도착 시간
bus_list = [540]
for i in range(n-1):
bus_list.append(bus_list[-1]+t)
Python
복사
•
그리고 크루 인원들의 도착 시간을 분 기준으로 변경하고 정렬하였다.
# 분 기준으로 크루 인원들 도착 시간 변경
timetable = str_to_time(timetable)
timetable = sorted(timetable) # 정렬 필요
Python
복사
•
그 다음 각 버스에 대하여 탑승 크루들의 도착 시간을 리스트로 만들어서 저장하였다.
예를 들어 09:00에 도착하는 버스(가장 먼저 오는 버스)에 08:59, 09:00 인원이 탑승했다면,
[[539, 540], ... ]
Python
복사
이런식으로 저장하였다.
•
저장의 기준은 정원이 다 차지 않았고, 버스 도착 시간보다 일찍 도착한 경우이다. 이때 while문을 활용해주었다.
for b in range(len(bus_list)):
r = 0
temp = []
# 정원이 다 차지 않았거나, 검색 범위 내인 경우 확인
while (r < m) & (c < len(timetable)):
if timetable[c] <= bus_list[b]: # 버스 도착 시간보다 일찍 도착한 경우
temp.append(timetable[c]) # 탑승 시킴
r += 1 # 정원 +1
c += 1 # 검색 범위 이동
else:
break # 버스 도착 시간보다 늦게 도착한 인원이 발견되면 다음 버스로 이동
take_list[b] = temp # 탑승 리스트 업데이트
Python
복사
•
그리고 맨 마지막 버스의 탑승 크루들의 도착 시간을 확인하여 만약 맨 마지막 버스가 정원이 다 차지 않은 경우 맨 마지막 버스의 도착 시간을 출력하고 맨 마지막 버스의 정원이 다 찬 경우 맨 마지막 버스에 가장 늦게 탑승한 인원보다 1분만 더 일찍 오면 탈 수 있으므로 1을 빼서 출력하였다.
last_bus = len(bus_list)-1 # 맨 마지막 버스
if len(take_list[last_bus]) < m: # 정원이 다 차지 않은 경우
return time_to_str(bus_list[last_bus]) # 맨 마지막 버스 도착 시간에 탑승하면 된다.
else:
return time_to_str(take_list[last_bus][-1]-1) # 맨 마지막 버스에서 가장 늦게 탑승한 인원보다 1분 일찍 오면 된다.
Python
복사