[ 프로그래머스 ] 셔틀버스 파이썬python 풀이

 

 

// 문제 요약

 

하루에 n번 t분 간격으로 오는 버스가 m 명을 태울 수 있다.

 

버스를 타는 사람들이 언제 줄을 서는지 알고 있을때

 

버스를 가장 늦게 탈 수 있는 시각을 구해라.

 

 

// 문제 풀이

 

이 문제는 악랄한(?) 마음을 가지고 풀면 잘 풀린다.

 

잠을 줄이기는 싫으나 얌체가 되어서 한 놈을 탈락시키더라도 내가 꼭 타고 만다

 

이런 마인드 셋으로 접근해야 모든 경우의 수를 발견할 수 있다...

 

실재로 함수의 리턴부분을 생각할때

 

주요한 알고리즘을 설계하는 것 보다 더 섬세하게 조건을 찾아야하는 문제였다.

 

코드는 아래와 같다.

 

source code github : https://url.kr/jblkau

hyun06000/coding_test_study_with_python

def solution(n, t, m, timetable):
    def M_to_HHMM(M):
        H, M = divmod(M, 60)
        return "{0:02d}:{1:02d}".format(H, M)

    M_table = []
    for tb in timetable:
        _tb = list(map(int, tb.split(":")))
        M_table.append(_tb[0] * 60 + _tb[1])
    M_table.sort()

    can_ride = []
    bus_M = 9 * 60
    for _ in range(n):
        _m = m  # 버스가 올때마다 자리가 새로 생긴다.
        while _m and M_table:
            head = M_table.pop(0)
            if head <= bus_M:
                _m -= 1
            else:
                M_table = [head] + M_table
                break

        if _m:  # 자리가 있고 사람이 없는 경우
            can_ride.append(min(bus_M + t - 1, 9 * 60 + t * (n - 1)))
        bus_M += t

    if not _m: # 마지막 버스에 사람이 모두 탄 경우
        return M_to_HHMM(head - 1) # 맨 마지막에 탄 사람보다만 일찍

    if can_ride:  # 자리가 있는 시간대가 있을 경우
        return M_to_HHMM(max(can_ride))  # 가능한 경우 중에서 가장 늦게

    else:  # 끝까지 기다려도 자리가 없는 경우
        return M_to_HHMM(head - 1)  # 맨 마지막에 탄 사람보다만 일찍

 

코드에 있는 주석을 따라가면 알 수 있겠지만

 

나는 이런 방식으로 풀이를 진행했다.

 

1. 매번 버스가 오고 자리가 생기므로 m을 매번 초기화 해준다.

2. 버스가 왔을때 탈 수 있는 사람 만큼 m을 지우고도 자리가 남으면 탈 수 있는 후보에 넣는다.

3. 후보를 모두 골랐는데 맨 마지막 버스가 만원이라 후보에 들어가지 못했다면

   가장 마지막에 탄 사람보다 1분 일찍 도착한다.

4. 맨 마지막 버스까지 후보에 있다면 자리가 있는 시간 중에서 가장 마지막 시간을 선택한다.

 

 

블로그에 글을 적으면서 생각을 하니까

 

맨 마지막 조건과 첫번째 조건이 같은 것이라는 생각이 든다.

 

하지만 마지막 버스에 자리가 없는 경우가 더 포괄적인 경우이므로

 

이것을 살리고 마지막 조건은 지워도 되겠다.

 

카카오의 풀이를 보면 쉬운문제라고 생각해서 난이도 중으로 설정을 했는데

 

너무 많이 틀려서 놀랐다고 한다 ㅎㄷㄷ...

 

섬세하게 잘 풀면 풀리는 문제이긴 하다.