문제 설명
카카오에서는 무료 셔틀버스를 운행하기 때문에 판교역에서 편하게 사무실로 올 수 있다. 카카오의 직원은 서로를 '크루'라고 부르는데, 아침마다 많은 크루들이 이 셔틀을 이용하여 출근한다.
이 문제에서는 편의를 위해 셔틀은 다음과 같은 규칙으로 운행한다고 가정하자.
- 셔틀은
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 solution(n, t, m, timetable):
answer = ''
time_list=[]
for time in timetable:
split=time.split(":")
s_hour=split[0]
s_min=split[1]
hour=int(s_hour[0])*10+int(s_hour[1])
minute=int(s_min[0])*10+int(s_min[1])
converted=hour*60+minute#convert 1hour => 60minute
time_list.append([converted,time])#[conveted time, original time]
time_list.sort(key=lambda x:x[0])#sort by converted time
bus=540#bus starts at 9:00
wait_idx=0#if bus arrive, then time_list[wait_idx] is the first
kon_choose=0
arrival=0#bus arrival count
while arrival<n:
candidate=[]#people who can get on the bus
candidate_idx=0#from wait_idx to wait_idx+m
while wait_idx+candidate_idx<len(time_list) and candidate_idx<m:
if time_list[wait_idx+candidate_idx][0]<=bus:#if can get on the bus,
candidate.append(time_list[wait_idx+candidate_idx])
else:#if can't get on the bus, then stop.
break
candidate_idx=candidate_idx+1
wait_idx+=candidate_idx
if len(candidate)==0 or len(candidate)<m:#if can get on the bus enoughly,
kon_choose=bus#then choose exact bus arrival
else:#if competition,
for c in candidate:
kon_choose=max(kon_choose,c[0]-1)
#then choose latest time -1
bus=bus+t#bus arrive after t minute
arrival=arrival+1
choose_hour=kon_choose//60
choose_min=kon_choose%60
answer=answer+str(choose_hour).zfill(2)
answer+=":"
answer=answer+str(choose_min).zfill(2)
return answer해설
1. 입력 받은 HH:MM을 분으로 변환하자. 그리고 오름 차순 정렬하자.
time_list=[]
for time in timetable:
split=time.split(":")
s_hour=split[0]
s_min=split[1]
hour=int(s_hour[0])*10+int(s_hour[1])
minute=int(s_min[0])*10+int(s_min[1])
converted=hour*60+minute#convert 1hour => 60minute
time_list.append([converted,time])#[conveted time, original time]
time_list.sort(key=lambda x:x[0])#sort by converted time분으로 변환한 이유는 계산하기 편하게 하기 위해서다.
예를 들어, 09:00은 540, 09:01은 541과 같이 0부터 시작되는 정수 단위로 표현되기 때문에 계산이 훨씬 쉬워진다.
이를 오름차순 정렬하면 0부터 시작해서 23*60+59 까지의 범위 안에 있는 시간의 흐름을 표현할 수 있다.
2.버스의 시작과 끝을 표현한다.
bus=540#bus starts at 9:00
arrival=0#bus arrival count
while arrival<n:
bus=bus+t#bus arrive after t minute
arrival=arrival+13. 버스의 시작과 끝 안에서 콘이 버스를 탈 수 있는 케이스를 찾는다.
bus=540#bus starts at 9:00
wait_idx=0#if bus arrive, then time_list[wait_idx] is the first
kon_choose=0
arrival=0#bus arrival count
while arrival<n:
candidate=[]#people who can get on the bus
candidate_idx=0#from wait_idx to wait_idx+m
while wait_idx+candidate_idx<len(time_list) and candidate_idx<m:
if time_list[wait_idx+candidate_idx][0]<=bus:#if can get on the bus,
candidate.append(time_list[wait_idx+candidate_idx])
else:#if can't get on the bus, then stop.
break
candidate_idx=candidate_idx+1
wait_idx+=candidate_idx
if len(candidate)==0 or len(candidate)<m:#if can get on the bus enoughly,
kon_choose=bus#then choose exact bus arrival
else:#if competition,
for c in candidate:
kon_choose=max(kon_choose,c[0]-1)
#then choose latest time -1
bus=bus+t#bus arrive after t minute
arrival=arrival+1먼저 탈 수 있는 후보들을 candidate라고 하자. 그리고 버스를 대기하는 가장 첫 번째 사람의 인덱스를 wait_idx라 하자. 그러면 후보들은 wait_idx 부터 시작해서 m명이다.
후보를 다 뽑았으면, 콘은 실제로 타는 것이 아니고 "결정"하는 것이므로 다음 wait_idx는 wait_idx+m이여야 한다.
만약, 기다리는 사람이 없거나 m명이 안되면, 게으른 콘은 가장 늦은 시각을 택할 것이므로 여유롭게 버스 정각에 타려고 "결정"할 것이다. (그리디)
기다리는 사람이 m명이라면 어떻게 해야 할까?
가장 늦은 시각을 택하는 콘의 입장에서 버스를 타려면, candidate 중 가장 늦은 시각부터 대기한 사람보다는 1분 빨리 와야 탈 수 있다.(그리디)
4.구한 분 단위를 HH:MM으로 다시 변환하여 리턴하자.
choose_hour=kon_choose//60
choose_min=kon_choose%60
answer=answer+str(choose_hour).zfill(2)
answer+=":"
answer=answer+str(choose_min).zfill(2)
return answer문자열.zfill(n)을 하면, 전체 길이가 n이 될 때 까지 왼쪽에 '0'을 붙여준다.
위 코드에서는 zfill(2)이므로 문자열 길이가 2가 될때까지 왼쪽에 '0'을 붙인다.
테스트 케이스 예시
timetable ["08:00","09:07","09:09","09:10","09:14","09:14","09:16"]
n=3
t=10
m=2
1.bus 09:00 도착
탑승 후보 08:00
콘 결정 시각 09:00
2.bus 09:10도착
탑승 후보 (09:07, 09:09, 09:10)
콘 결정 시각 09:09
3.bus 9:20 도착 (09:10 탑승객은 탄 상태다.)
탑승 후보 (09:14, 09:14, 09:16)
콘 결정 시각 9:15
정답: "09:15"느낀 점
1.코드를 작성하기 전에 수기로 설계하자.
코딩 테스트 문제는 복잡하고 어려운 문제다. 수기로 꼼꼼히 설계하지도 않고 코딩부터 하면 반드시 망한다.
수기로 깔끔히 설계가 이루어진 후 코딩에 들어가야만 문제 풀이에 있어서 헤메지 않으며 시간 낭비가 확연히 없어진다.
다른 말로하면, 시험 볼 때 수기로 정확히 안 풀리는 문제가 있으면 넘어가라.
2.결과의 검증은 반드시 수기로 하자.
결과가 확실하게 나오는지도 반드시 수기로 검증하자.
이번 문제는 쓸데없이 검증에 있어서 헤맸었다. 후보자 m명을 뽑을 때, candidate_idx와 wait_idx, 후보자 시간들이 정확하게 안나왔다.
멍청하게도 수기 검증 없이 print()와 코드 실행만 돌려서 2시간 정도를 낭비했다.
하지만 수기로 적어가며 꼼꼼히 검증하니, 정확한 인덱스와 후보자 시간들을 훨씬 쉽게 구할 수 있었다.
또한 자기가 만든 테스트 케이스도 과연 정확한지도 꼼꼼히 수기로 검증해야 한다.
이 문제의 경우, 내가 만든 테스트 케이스도 다시 검증해보니 틀린 기대값이었다.
이런 실수가 없도록 하자.
3.효율성을 먼저 생각하기보단, 정확성과 간결함을 우선하자.
이 문제를 처음 풀 때, 효율성을 높이기 위해 큐(deque())를 이용하려 했다. 후보자를 꺼내고 다시 넣는데 O(1)이었기 떄문이다.
하지만 이 문제는 단순히 time_list를 순회하며 조회하기만 하면 된다. 오히려 큐를 이용하면 구현이 훨씬 까다로워지며 결국 시간복잡도도 단순 조회와 같은 O(N)이다.
이러한 폐해는 효율성을 먼저 생각하기 때문에 발생한다.
O(N)으로 절대 풀 수 없다고 생각이 들 때에만 O(logN)의 풀이 방식을 이용해 풀어야 덜 헤멘다.
O(N)으로 풀 수 있는 문제인 것 같으면 O(N)의 풀이 방식으로 풀자. 그래야 정확성과 간결함이 훨씬 높아진다.
그리고 제출했을 때 정확성이 맞고 효율성만 실패라면 그제서야 효율성을 높이면 된다.
단, 입력 개수가 최대 100억이라던지 그러면 효율성을 먼저 따지긴 해야 한다.
다시 풀기 1회 정답 코드
def convert_time_to_int(str_time):
hour,minute=str_time.split(':')
if hour[0]=='0':
hour=hour[1]
if minute[0]=='0':
minute=minute[1]
return int(hour)*60+int(minute)
def convert_int_to_time(int_time)->str:
hour=int_time//60
minute=int_time%60
hour=str(hour)
if len(hour)==1:
hour=hour.zfill(2)
minute=str(minute)
if len(minute)==1:
minute=minute.zfill(2)
return hour+":"+minute
def solution(n, t, m, timetable):
# HH:MM -> 값으로 치환 후 정렬
int_timetable=[]
for time in timetable:
int_timetable.append(convert_time_to_int(time))
int_timetable.sort()
kon_time=0
bus_time=540
# 대기열 인덱스를 뜻함.
index=0
# i 번째 버스가 온다.
for i in range(n):
can_get_on=[]
# 대기열 인덱스 ~ 대기열 인덱스 + m 만큼 확인한다.
for j in range(m):
if index+j<len(int_timetable) and int_timetable[index+j]<=bus_time:
can_get_on.append(int_timetable[index+j])
# i 번째 버스에 타는 사람이 있을 경우
if len(can_get_on):
# m개가 안된다면, 해당 버스 정각에 타면 된다.
if len(can_get_on)<m:
kon_time=bus_time
else:
# m개가 되서 못타면, 제일 늦게 탄 크루 -1 분만큼 빨리 오면 된다.
kon_time=can_get_on[-1]-1
# i+1 번째 버스의 대기열을 확인해야하므로 다음 인덱스로 넘긴다.
index+=len(can_get_on)
# i 번째 버스에 아무도 안 탄 경우, 콘이 해당 버스를 그 시각에 타면 탈 수 있다.
else:
kon_time=bus_time
bus_time+=t
return convert_int_to_time(kon_time)