코딩 테스트(Python) 2018 KAKAO BLIND RECRUITMENT[1차] 셔틀버스

문제 설명

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

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

• 셔틀은 09:00부터 총 n회 t분 간격으로 역에 도착하며, 하나의 셔틀에는 최대 m명의 승객이 탈 수 있다.
• 셔틀은 도착했을 때 도착한 순간에 대기열에 선 크루까지 포함해서 대기 순서대로 태우고 바로 출발한다. 예를 들어 09:00에 도착한 셔틀은 자리가 있다면 09:00에 줄을 선 크루도 탈 수 있다.

일찍 나와서 셔틀을 기다리는 것이 귀찮았던 콘은, 일주일간의 집요한 관찰 끝에 어떤 크루가 몇 시에 셔틀 대기열에 도착하는지 알아냈다. 콘이 셔틀을 타고 사무실로 갈 수 있는 도착 시각 중 제일 늦은 시각을 구하여라.

단, 콘은 게으르기 때문에 같은 시각에 도착한 크루 중 대기열에서 제일 뒤에 선다. 또한, 모든 크루는 잠을 자야 하므로 23:59에 집에 돌아간다. 따라서 어떤 크루도 다음날 셔틀을 타는 일은 없다.

 

def solution(n, t, m, timetable):
    answer = 0  # 마지막으로 탑승해야 할 시간 (최종 답)
    
    # timetable을 분 단위로 변환 (시:분 → 분으로 계산)
    timetable = [60 * int(i[:2]) + int(i[3:]) for i in timetable]
    timetable.sort()  # 크루의 탑승 시간 오름차순으로 정렬
    
    # 버스 운행 시간 (9시부터 시작하여 n번 버스까지 t 간격으로 운행)
    bustime = [60 * 9 + i * t for i in range(n)]  # 9:00부터 n번 버스까지의 시간 리스트
    
    i = 0  # 크루의 인덱스, 버스에 탑승할 크루를 추적
    for bt in bustime:  # 각 버스의 운행 시간에 대해 반복
        cnt = 0  # 현재 버스에 탑승한 크루 수
        
        # 버스에 탈 수 있는 크루를 찾아서 탑승시키기
        while i < len(timetable) and timetable[i] <= bt and cnt < m:
            i += 1  # 탑승한 크루 수 증가
            cnt += 1
        
        if cnt < m:  # 버스에 자리가 남으면
            answer = bt  # 현재 버스 시간에 탑승할 수 있음
        else:  # 버스에 자리가 없으면
            # 마지막 탑승한 크루보다 1분 전에 도착해야 함
            answer = timetable[i - 1] - 1
    
    # 답을 시:분 형식으로 변환 (2자리로 맞추기 위해 zfill 사용)
    answer = str(answer // 60).zfill(2) + ":" + str(answer % 60).zfill(2)
    
    return answer  # 최종 답 반환