[프로그래머스] 카카오 블라인드 리쿠르트 2018 - 셔틀 버스 (Python)

 

코딩테스트 연습 - [1차] 셔틀버스

카카오에서는 무료 셔틀버스를 운행하기 때문에 판교역에서 편하게 사무실로 올 수 있다. 카카오의 직원은 서로를 '크루'라고 부르는데, 아침마다 많은 크루들이 이 셔틀을 이용하여 출근한다.

이 문제에서는 편의를 위해 셔틀은 다음과 같은 규칙으로 운행한다고 가정하자.

• 셔틀은 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"]	"18:00"

---

풀이

timetable을 빠른 시간 순서대로 정렬하여 deque에 저장한 다음,

셔틀 버스가 오는 시간마다 미리 온 탑승자들을 m을 넘지 않는 만큼 앞에서부터 pop하여 탑승자들을 제거 하고,

이 때마다 마지막 탑승자의 시간을 last라는 변수에 저장하도록 하였다.

 

마지막 버스에 아직 자리가 남았는데도 남아있는 탑승자가 없다면 마지막 버스가 도착하는 시간을 정답으로 출력한다.

하지만, 자리가 남지 않았다면 마지막 탑승자보다 1분 먼저 일찍 나와야 하기 때문에 마지막 탑승자의 대기 시간인 last에 1분을 차감한 시간을 정답으로 출력한다.

 

 

(선 구현 해두고, 통과 못하는 원인 찾아갈 심산으로 코드를 짰는데 통과해버리기도 했고, 나와 같은 풀이로 푼 사람도 없는 것 같아 조금 찝찝했던 문제였다...)

 

 

코드

import collections

def convert_timetable_to_miniute(time):
    result = []
    hour = str(time // 60)
    minuite = str(time % 60)
    
    if len(hour) < 2:
        result.append('0')    
    result.append(hour)
    
    result.append(':')
    
    if len(minuite) < 2:
        result.append('0')    
    result.append(minuite)
    
    return ''.join(result)

def convert_minuite_to_timetable(time):
    hour = int(time.split(':')[0])
    minuite = int(time.split(':')[1])
    return hour * 60 + minuite

def solution(n, t, m, timetable):
    answer = ''
    timetable = collections.deque(sorted(timetable))
    
    now = 540
    last = ''
    count = 0
    
    for i in range(n):
        count = 0
        while timetable and convert_minuite_to_timetable(timetable[0]) <= now and count < m:
            last = timetable.popleft()
            count += 1
        now += t
    
    if count >= m:
        return convert_timetable_to_miniute(convert_minuite_to_timetable(last) - 1)
    
    now -= t
    return convert_timetable_to_miniute(now)

코드를 조금 보완한다고 하면 시간 -> 문자열을 바꾸는 메소드를 format() 함수를 이용하여 조금 더 간단하게 작성할 수 있을 것 같다.