Programmers - [1차] 셔틀 버스

문제 링크

하루 동안의 셔틀버스 탑승을 시뮬레이션 하는데 00:00 ~ 23:59로 O(3600)
경우의 수도 마찬가지로 00:00 ~ 23:59 로 3600개이다
총 O(3600*3600) = O(12960000) 으로 모든 경우를 시뮬레이션 해도 시간복잡도는 충분하다.

시뮬레이션 시작시간과 종료시간을 적절하게 잘라보려 했지만 까다로워서 그냥 모든 시간을 시뮬레이션 했다.
(버스가 너무 많아서 23:59에 도착해도 가능한 경우, 버스는 적은데 00:00부터 대기하는 사람이 많은 경우 등 고려할 것이 많음)

from collections import deque

def solution(n, t, m, timetable):
    answer = ''
    for time in range(0, to_minutes("23:59")+1):
        (possible, time) = simulation(n, t, m, timetable, time)
        if possible:
            answer = time

    return answer

def to_minutes(time):
    [hour, minutes] = time.split(":")
    return (int(hour) * 60) + int(minutes)

def to_time(minutes):
    hh = minutes//60
    hh_str = str(hh) if hh >= 10 else '0'+str(hh)
    mm = minutes % 60
    mm_str = str(mm) if mm >= 10 else '0'+str(mm)

    return hh_str+":"+mm_str

def simulation(n, t, m, timetable, con):

    shuttle = deque([to_minutes("09:00") + i*t for i in range(n)])
    without_con = sorted(
        list(map(lambda x: (to_minutes(x), False), timetable)))

    con_index = len(without_con)+1
    for (i, value) in enumerate(without_con):
        if value[0] > con:
            con_index = i
            break

    crews = deque(without_con[:con_index] +
                  [(con, True)] + without_con[con_index:])

    current = 0

    while current <= to_minutes("23:59"):
        if len(shuttle) == 0 or len(crews) == 0:
            break

        # 탑승 시간이 된 경우
        if current == shuttle[0]:
            for _ in range(min(len(crews), m)):
                if crews[0][0] <= current:
                    # 콘이 탑승한 경우
                    if crews[0][1]:
                        return (True, to_time(con))
                    crew = crews.popleft()
                    # print(to_time(current), crew, "in")

            shuttle.popleft()

        current += 1

    return (False, "xxxx")