[1차] 셔틀버스

https://programmers.co.kr/learn/courses/30/lessons/17678

• 문제

  • 09:00 부터 n 회 t 분 간격으로 버스가 오며 버스는 최대 m 명 태울 수 있다.

  • 사람들이 정류장에 오는 시간 리스트 timetable 이 주어진다.

  • 콘과 같은 시간에 온 크루 중에는 가장 마지막에 버스를 탄다.

  • 콘이 사무실에 갈 수 있는 시간중 가장 늦은 시간은 언제일까?

• aps

  1. 목표지향적으로 보자. 콘은 마지막 버스를 타야한다.

  2. 마지막 버스를 고려하기 위해, 마지막 버스가 오기전 버스들이 태우고 가는 크루들을 먼저 처리하자

  3. 자, 이제 마지막 버스와, 앞서 지나간 버스들이 태워가지 못 한 승객들만이 남았다.

  4. 여기서 모든 경우의 수를 살펴보면 ( 그림으로 그려봐야 놓치지 않는다. )

     1. 남은 승객

        • 남은 승객이 m 미만

        • 남은 승객이 m 이상

     2. 분포시간

        • 남은 승객의 첫번째 승객이 버스 도착시간보다 늦게

        • 남은 승객의 첫번째 승객이 버스 도착시간보다 빠르게

          • 남은 승객의 m번째 승객이 도착시간보다 빠르게

          • 남은 승객의 m번째 승객이 도착시간보다 늦게

  5. 각 경우의 수중 상황마다 공통적으로 처리되는 것을 발견할 수 있다.

     • 남은 승객의 첫번째 승객이 도착시간보다 늦다 or 남은 승객이 m 미만이다 or m 번째 승객의 1분 앞선 시간이 도착시간보다 늦을 때

       • python 의 동기적 특성으로 앞선 조건문부터 차례대로 수행하게 되어 전부 return 마지막 버스의 도착시간 이다.

     • 그 외에는

       • m 번째 승객보다 1분 앞선 시간을 return 함을 알 수 있다.

  6. 기본적으로 완탐이고 완탐 중 우선 수행할 ( 큼지막한 ) 것부터 해결하면, 나머지는 알아서 처리되는 것을 꼼꼼히 파악하는 것이 key

def solution(n, t, m, timetable):
    c = [] # 전처리
    for r in timetable:
        c.append((int(r[0:2]) * 60) + (int(r[3:5])))
    c.sort()

    for i in range(n): # 버스마다 for 문
        b = 540 + (i * t) # 매 버스의 도착시간
        if i == n - 1: # 마지막 버스라면
            if c[0] > b or len(c) < m or c[m - 1] - 1 > b: # 남은 승객의 첫번째가 버스도착시간보다 늦다면, 그렇지않고 남은 승객수가 m보다 작다면, 그렇지도 않고, m번째 승객보다 1분 빠른 시간이 도착시간보다 늦다면
                return '{:02d}:{:02d}'.format(b // 60, b % 60) # 버스도착시간 반환
            b = c[m - 1] - 1 # m번째 승객의 시간보다 1분 빨리
            return '{:02d}:{:02d}'.format(b // 60, b % 60)

        for j in range(m): # 버스올때마다 태울수 있는 승객 지우기
            if c[0] <= b:
                c.pop(0)
            else:
                break