문제 설명
문제는 이 곳 링크를 참조하길 바란다.
전체 코드
참조한 코드
def solution(n, t, m, timetable):
answer = ''
crew = [ int(tt.split(":")[0])*60+int(tt.split(":")[1]) for tt in timetable ]
# 크루의 도착시간
crew.sort()
# bus[x] = (버스시간, 승객 수, 마지막 탄 크루의 도착시간)
bus = [ (540+t*i, 0, None) for i in range(n)]
bidx, cidx = 0, 0
while cidx < len(crew):
c = crew[cidx]
if bidx == len(bus):
break
if c <= bus[bidx][0] and bus[bidx][1] < m:
tt, cnt, _ = bus[bidx]
bus[bidx] = (tt, cnt+1, c)
cidx += 1
else:
bidx += 1
ret = bus[-1][0]
if bus[-1][2]:
if bus[-1][1] == m:
ret = bus[-1][2] - 1
return '%02d:%02d' % (ret // 60, ret % 60)해결 방법
진짜.... 카카오 문제는 너무 어렵다. 내가 설명하는 것보다 설명이 아주 잘되어 있는 분의 설명을 가져왔다.
1. 시간 변수 관리
이 문제에서 주어진 핵심 변수들은 모두 "시간" 으로 표현이 되어 있다.
셔틀이 처음 출발하는 시간 , 크루원들이 대기열에 도착하는 시간 , 우리가 구해야 하는 정답 모두 "시간"의 개념으로 표시가 되어 있다. 하지만 ! 시간이 int형 자료형이 아닌 문자열 형태로 주어지게 된다. 조금 더 구체적으로 이야기해보면 HH:MM 형태로 "시"와 "분"의 형태로 주어지게 된다.
문자열로 숫자가 주어지기 때문에, 본인은 이를 간편하게 계산하기 위해서 모두 "분" 단위로 변환 후 계산을 진행해 주었다.
"HH:MM" 이라는 문자열이 주어진다면 이를 분 단위의 시간으로 바꾸게 되면 HH * 60 + MM 으로 표현할 수 있다.
이런식으로 변환을 하게 되면 첫 번째 셔틀이 출발하는 시간은 "540"이 된다. 09:00에 처음으로 출발을 하기 때문이다.
2. Solution
본인은 크루원들이 대기열에 도착하는 시간을 #1의 과정을 통해 '분'단위로 모두 통일 후 오름차순으로 정렬시켜 주었다.
크루원들이 대기열에 도착하는 시간이 오름차순으로 주어진다는 이야기가 없으므로, 크루원들의 도착시간을 오름차순으로 관리해 주었고, 이 오름차순으로 정렬되어 있는 크루원들 시간들 사이에 콘이 들어갈 시간을 찾으면 되는 것이다.
그렇다면, 콘이 셔틀을 타기 위해서 가장 늦게 도착할 수 있는 시간을 한번 구해보자.
콘이 가장 늦게 출근을 하기 위해서는 무조건적으로 "가장 마지막 셔틀에 탑승하는 것" 이 유리할 것이다.
즉 ! 우리는 콘을 반드시 가장 마지막 셔틀에 탑승하게 만들 것이다. 지금부터 이 과정을 크게 2가지 경우로 나눠서 생각을 해보자.
1. 마지막 셔틀에 자리가 남는 경우
가장 마지막 셔틀에 딱 맞춰서 크루원들이 다 탔을수도 있고, 그 전 셔틀에 이미 탑승을 완료했을 수도 있다. 이건 상관이 없다. 중요한건, "가장 마지막 셔틀에 자리가 남는 다는 것" 이다. 가장 마지막 셔틀에 자리가 남는다면 이 셔틀버스를 타고 가면 된다.
즉 ! 이 때의 정답은 "가장 마지막 셔틀이 도착하는 시간"이 될 것이다. 가장 마지막 셔틀이 도착하는 시간에만 대기열에 들어가 있으면 가장 마지막 셔틀을 탈 수 있음을 의미하기 때문이다.
"마지막 셔틀에 자리가 남을 경우 , 콘이 줄을 서야 하는 시간은 가장 마지막 셔틀이 도착하는 시간"
2. 마지막 셔틀에 자리가 남지 않는 경우
마지막 셔틀에 자리가 남지 않는다면, 콘은 출근을 할 수 없음을 의미한다. 즉 ! 이 경우에는 콘이 크루원들이 도착하는 시간 중간 어디간에 먼저 도착을 해 있어야만 마지막 셔틀을 탈 수 있음을 의미한다.
그럼 한가지 예를 가지고 생각을 해보자.
ex_A)
마지막 셔틀 버스가 5분에 도착하고 현재 줄을 서 있는 크루원이 [ 4분 , 5분 ] 에 도착한 2명의 크루원이 있다고 가정해보자.
그리고 셔틀버스의 탈 수 있는 최대 크루원의 수는 2명이라고 가정해보자.
콘을 제외하고 생각한다면, 4분과 5분에 도착한 크루원 2명이 마지막 셔틀버스를 탈 것이다. 하지만 우리는 콘을 반드시 탑승을 시켜야 한다. 그렇다면 콘은 몇 분에 줄을 서야할까 ?? 4분에 줄을 서면 될 것이다.
그렇게 되면 현재 줄을 서 있는 크루원이 [ 4분 , 4분(콘) , 5분 ] 형태로 될 것이고, 마지막 셔틀버스에 콘이 탈 수 있을 것이다.
한가지 상황을 더보자.
ex_B)
마지막 셔틀버스가 5분에 도착하고 현재 줄을 서 있는 크루원이 [ 5분 , 5분 , 6분 ] 에 도착한 3명의 크루원이 있다고 가정해보자. 그리고 셔틀 버스의 탈 수 있는 최대 크루원의 수는 2명이라고 가정해보자.
콘을 제외하고 생각한다면, 5분에 줄을 선 크루원 2명이 탑승을 할 것이다. 콘이 탑승하기 위해서는 4분에 줄을서야 할 것이다.
왜냐하면 ! 5분에 줄을 서게 되면 "같은 시간에 도착한 크루원들 중에서는 가장 마지막에 줄을 서는 콘의 특징" 때문에 셔틀버스를 탈 수 없게 될 것이다.
그럼 콘이 셔틀버스를 탈 수 있는 구체적인 시간을 이야기해보자.
바로 ! "가장 마지막에 탑승한 크루원의 시간 - 1"을 한 시간이 콘이 셔틀버스를 탈 수 있는 시간이 된다.
ex_A)에서 가장 마지막에 탑승한 크루원의 시간은 '5분' 이였다. 그리고 콘이 셔틀버스를 탈 수 있는 시간은 5 - 1 = 4분이었다.
ex_B)에서 가장 마지막에 탑승한 크루원의 시간은 '5분' 이였다. 그리고 콘이 셔틀버스를 탈 수 있는 시간은 5 - 1 = 4분이었다.
"마지막 셔틀에 자리가 남지 않는 경우, 콘이 줄을 서야 하는 시간은, 콘을 제외하고 생각했을 때, 셔틀버스를 탑승한 마지막 크루원의 시간 - 1"
출처: https://yabmoons.tistory.com/637 [얍문's Coding World..]
