[Programmers/파이썬]프로그래머스(Lv.3) 셔틀버스 문제풀이
셔틀버스
카카오에서는 무료 셔틀버스를 운행하기 때문에 판교역에서 편하게 사무실로 올 수 있다. 카카오의 직원은 서로를 '크루'라고 부르는데, 아침마다 많은 크루들이 이 셔틀을 이용하여 출근한다.
이 문제에서는 편의를 위해 셔틀은 다음과 같은 규칙으로 운행한다고 가정하자.
- 셔틀은 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 사이의 값이 될 수 있다.
입출력 예제
n t m timetable answer
| 1 | 1 | 5 | ["08:00", "08:01", "08:02", "08:03"] | "09:00" |
| 2 | 10 | 2 | ["09:10", "09:09", "08:00"] | "09:09" |
| 2 | 1 | 2 | ["09:00", "09:00", "09:00", "09:00"] | "08:59" |
| 1 | 1 | 5 | ["00:01", "00:01", "00:01", "00:01", "00:01"] | "00:00" |
| 1 | 1 | 1 | ["23:59"] | "09:00" |
| 10 | 60 | 45 | ["23:59","23:59", "23:59", "23:59", "23:59", "23:59", "23:59", "23:59", "23:59", "23:59", "23:59", "23:59", "23:59", "23:59", "23:59", "23:59" |
사고 흐름
1. 도착한 순서대로 버스에 넣고 마지막 버스에 제일 늦게 버스에 타는 시간을 구하는 문제
2. 처음에는 counter를 사용해서 문제풀이를 시도했지만, 하드코딩이 예상돼서 방법을 바꿨다.
3. 단순하게 생각해 버스 시간 전에 있는 사용자들을 최대한 넣고, m이 넘어가면 다음 버스에 넣고, 그런 식으로 진행.
3-1. 딕셔너리를 만들어 버스 시간과 버스에 탈 사람의 시간을 넣고 진행
3-2. 모든 정보를 넣고, 마지막 버스에서 마지막 시간을 구함
문제 핵심과 알고리즘
문자열 추출(활용)과 버스 시간과 사람들의 시간을 비교하는 리스트 활용 문제
import re
def solution(n, t, m, timetable):
answer = ''
bustime={}
time=[]
for i in range(n) : #버스 시간: [버스 타는 사람 시간]
bustime[540+i*t]=[]
timetable.sort() #빨리 온 순서대로 처리하기 위해
for t in timetable : #각 사용자(시간)에 대해
hour,minu=t.split(':')
times=int(hour)*60+int(minu)
for k,v in bustime.items() :
if k>=times and len(bustime[k])<m : #버스 시간보다 빨리오고, 버스에 자리가 남았다면
bustime[k].append(times)
break
for i,(k,v) in enumerate(bustime.items()) : #버스에 탄 딕셔너리를 돌면서
if i==len(bustime)-1 : #마지막 버스 시간에서
if len(bustime[k])==m : #버스가 꽉찼다면, 마지막 사람의 시간보다 일분 빠르게
answer=bustime[k][-1]-1
else : #버스에 자리가 있다면, 버스 시간에 맞춰
answer=k
return str(answer//60).zfill(2)+':'+str(answer%60).zfill(2)문제 풀면서 헤맸던 부분
1. 변수명 중복
처음에 문자열에서 시와 분을 가져올때 h와 m으로 가져왔는데, 입력 데이터 m과 중복돼 자꾸 에러가 났다. 여기서 시간이 좀 걸렸다.. 이런 어이없는 실수를 제발 하지말자,,!
다른 풀이 참고하며 배운 점
def solution(n,t,m,timetable):
timetable=[int(i[:2])*60+int(i[3:]) for i in timetable]
timetable.sort()
bustable=[9*60+t*i for i in range(n)]
for i in bustable:
passenger=[p for p in timetable if p<=i]
if i==bustable[-1]:
if len(passenger)>=m:
answer=passenger[m-1]-1
elif len(passenger)<m:
answer=i
else:
answer=passenger[-1]
elif len(passenger)<m:
timetable=timetable[len(passenger):]
elif len(passenger)>=m:
timetable=timetable[m:]
answer= str(divmod(answer,60)[0]).rjust(2,'0')+':'+str(divmod(answer,60)[1]).rjust(2,'0')
return answer이 풀이에서는 좀더 직관적으로 리스트 슬라이싱을 이용해, 사용자 리스트 길이가 m보다 크면 m에서 잘라서 그 이후에 리스트에서 진행했다. 이렇게 보니까 되게 쉬운 문제 같다..
총평
레벨3라고 겁을 먹고 조금 어렵게 생각했던 것 같다. 문제 그대로 따라가면 어려운 문제가 아닌데.. 핵심은 정렬을 한 후에 (기다린 순서대로) m만큼씩 자르면서 확인하는것!