[프로그래머스] Lv3. 셔틀버스 (2018 카카오 공채)

🔗

풀이

최대한 셔틀을 늦게 타야 하므로 사실상 마지막 버스를 탈수록 정답에 가깝다. 하지만 다른 크루들과 같은 시간에 도착한다면 그 중에서는 가장 마지막이라고 한다. 그렇다면 모두가 9시에 왔고, 먼저 도착한 크루들의 인원이 셔틀의 인원과 정확하게 딱 맞아 떨어진다면 콘은 셔틀을 탈 수 없다. 그보다는 일찍 나와야 하는 것이다.

그럼 반대로 일찍 나와서 기다리면서 셔틀에 크루들을 태워서 보내고, 태워서 보냄과 동시에 크루들의 시간이 바뀔 때마다 그에 맞춰서 증가시키는 건 어떨까? 만약 모든 크루가 9시에 나와있다면 콘의 시간은 8시 59분에 맞춰 있을 것이고, 모든 크루가 9시 이므로 그보다는 일찍 나왔으니 이번엔 콘은 셔틀을 탈 수 있을 것이다.

만약 모든 크루들이 셔틀의 시간에 맞춰 탈 수 없고, 콘만 탈 수 있는 상황이라면 콘은 마지막에 오는 셔틀을 타면 될 것이다. 이번에는 크루들의 시간이 아니라 셔틀의 시간에 콘의 시간을 맞춰야 한다.

즉, 크루들의 시간과 탈 수 있는 셔틀의 시간에 맞춰 매번 콘의 도착 시간을 업데이트하면 된다.

def convert(s):
    return int(s[:2])*60 + int(s[3:])

def rev_convert(n):
    h, m = map(str, divmod(n, 60))
    return f"{h.zfill(2)}:{m.zfill(2)}"

def solution(n, t, m, timetable):
    timetable = sorted(list(map(convert, timetable)), reverse=True)
    
    bus, ans = 540, 0
    while True:
        k = m
        while timetable and k and timetable[-1]<=bus:
            ans = timetable.pop()-1
            k -= 1
        
        if k>0:
            ans = bus
            
        if not timetable:
            break
        
        bus += t
        if bus>=540+n*t:
            break
        ans = min(bus-t, timetable[-1]-1)
    
    return rev_convert(ans)