카카오 2018 [1차] 셔틀버스

풀이

# 문제요약
## 셔틀은 09:00부터 총 n회 t분 간격으로 역에 도착하며
## 하나의 셔틀에는 최대 m명의 승객이 탈 수 있다.
## 가장 늦은 셔틀을 타고 사무실로 갈수 있는 시각을 구하자
## 같은 시각에 도착한 크루들이 있다면 대기열중에 제일 뒤에 선다.
## 다음날 셔틀을 타는 경우의수는 없다.

def solution(n, t, m, timetable):
    # timetable의 정렬이 필요하다
    ## 가장 빨리 도착한 크루부터 셔틀에 태워보기 위해서
    timetable = sorted([hmToM(time) for time in timetable])
    
    # crewIdx: 현재 탑승시도 하는 크루 인덱스
    # boarded: 현재 셔틀에 탑승한 인원, 매 셔틀마다 초기화 필요
    # answer: 답
    crewIdx, boarded, answer = 0, 0, 0
    
    # n, t, m을 통해 모든 셔틀의 출발시각을 알수 있다.
    for shrttle in range(540, 540+n*t, t):
        
        # 매 셔틀마다 idx를 증가시면서 탑승을 시킨다.
        while crewIdx < len(timetable):
            if timetable[crewIdx] > shrttle or boarded==m:
                break
            crewIdx += 1
            boarded += 1
        
        # 만약 셔틀에 자리가 남는다면 셔틀시간에 딱맞쳐 오면 된다!
        # 아니면 가장 마지막에 탑승한 인원보다 1분 일찍 오면 탑승할수 있다.
        answer = shrttle if boarded<m else timetable[crewIdx-1]-1
        
        # 다음에 도착하는 셔틀을 위해 초기화
        boarded = 0

    return mToHm(answer)

def hmToM(hm):
    hour, minute = hm.split(":")
    return int(hour)*60+int(minute)

def mToHm(m):
    hour, minute = str(m//60), str(m%60)
    hour = "0"+hour if len(hour)==1 else hour
    minute = "0"+minute if len(minute)==1 else minute
    return hour+":"+minute