셔틀버스

문제

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

접근 방식

처음에는 시간을 정수 형태로 변환하지 않고 풀었다가 틀렸다.

이 문제는 timetable을 sorting 하고 시간 간 비교를 하는 프로세스 때문에 무조건 정수 형태로 변환해서 푸는 게 정신에 이롭다!

두번째로 풀다가 또 깨달은 점은, 전에 풀때는 마지막 버스의 시간 범위 내에 있는 크루만 따지면 된다고 생각했는데, 생각해보니 그 범위에 속하지는 않지만 이전 버스를 타지 못하고 버스를 띄워보낸 크루들을 차례대로 태워야 한다.
이것 때문에 timetable 역시 sorting 해야 한다.

결국 모든 버스에 대해 차례대로 크루들을 태우고, 만약 마지막 버스의 인원이 꽉 차지 않았으면 마지막 버스의 도착 시각을 반환하면 되고, 그게 아니면 마지막 인원 -1분을 반환하면 된다.

코드

def solution(n, t, m, timetable):
    buses = [9 * 60]
    time = 9 * 60  # 시작 버스는 무조건 9시
    for _ in range(1, n):
        time += t
        buses.append(time)

    crews = []
    for crew in timetable:
        hr, mn = crew.split(':')
        crew_time = int(hr) * 60 + int(mn)
        crews.append(crew_time)
    crews.sort()

    crew_count = 0
    bus_idx, crew_idx = 0, 0
    last_crew_on_bus = -1  # 마지막 버스의 도착 시각
    last_crew_count = 0  # 마지막 버스에 탄 인원
    while bus_idx < len(buses) and crew_idx < len(crews):
        bus_cur = buses[bus_idx]
        if crews[crew_idx] <= bus_cur:  # 현재 사람 태울 수 있으면 태움
            if bus_idx == len(buses) - 1:  # 마지막 버스 기혹
                last_crew_on_bus = crews[crew_idx]
                last_crew_count += 1
            crew_idx += 1
            crew_count += 1
        else:  # 현재 버스를 탈 인원이 없음 -> 다음 버스로!
            crew_count = 0
            bus_idx += 1

        if crew_count >= m:  # 한 버스에 인원이 찬 경우, 다음 버스로!
            crew_count = 0
            bus_idx += 1

    ans = 0
    if last_crew_count < m: # 만약 인원이 덜 찼으면 마지막 버스 도착 시각
        ans = buses[-1]
    else: # 꽉 찼으면 마지막 인원 -1분
        ans = last_crew_on_bus - 1

    hr, mn = divmod(ans, 60)
    hr = '0' + str(hr) if hr < 10 else str(hr)
    mn = '0' + str(mn) if mn < 10 else str(mn)

    return hr + ':' + mn