[프로그래머스] 🚍 셔틀버스 - [1차] 2018 카카오 블라인드 채용 / Python / KAKAO BLIND RECRUITMENT

🚍 셔틀버스 - [1차] 2018 카카오 블라인드 채용 / Python / KAKAO BLIND RECRUITMENT

문제 설명

카카오에서는 무료 셔틀버스를 운행하기 때문에 판교역에서 편하게 사무실로 올 수 있다. 카카오의 직원은 서로를 '크루'라고 부르는데, 아침마다 많은 크루들이 이 셔틀을 이용하여 출근한다.

이 문제에서는 편의를 위해 셔틀은 다음과 같은 규칙으로 운행한다고 가정하자.

• 셔틀은 09:00부터 총 n회 t분 간격으로 역에 도착하며, 하나의 셔틀에는 최대 m명의 승객이 탈 수 있다.
• 셔틀은 도착했을 때 도착한 순간에 대기열에 선 크루까지 포함해서 대기 순서대로 태우고 바로 출발한다. 예를 들어 09:00에 도착한 셔틀은 자리가 있다면 09:00에 줄을 선 크루도 탈 수 있다.

일찍 나와서 셔틀을 기다리는 것이 귀찮았던 콘은, 일주일간의 집요한 관찰 끝에 어떤 크루가 몇 시에 셔틀 대기열에 도착하는지 알아냈다. 콘이 셔틀을 타고 사무실로 갈 수 있는 도착 시각 중 제일 늦은 시각을 구하여라.

단, 콘은 게으르기 때문에 같은 시각에 도착한 크루 중 대기열에서 제일 뒤에 선다. 또한, 모든 크루는 잠을 자야 하므로 23:59에 집에 돌아간다. 따라서 어떤 크루도 다음날 셔틀을 타는 일은 없다.

입력 형식

셔틀 운행 횟수 n, 셔틀 운행 간격 t, 한 셔틀에 탈 수 있는 최대 크루 수 m, 크루가 대기열에 도착하는 시각을 모은 배열 timetable이 입력으로 주어진다.

• 0 ＜ n ≦ 10
• 0 ＜ t ≦ 60
• 0 ＜ m ≦ 45
• timetable은 최소 길이 1이고 최대 길이 2000인 배열로, 하루 동안 크루가 대기열에 도착하는 시각이 HH:MM 형식으로 이루어져 있다.
• 크루의 도착 시각 HH:MM은 00:01에서 23:59 사이이다.

출력 형식

콘이 무사히 셔틀을 타고 사무실로 갈 수 있는 제일 늦은 도착 시각을 출력한다. 도착 시각은 HH:MM 형식이며, 00:00에서 23:59 사이의 값이 될 수 있다.

😃 풀이 1

def timeToMinute (time):
    lst = time.split(':')
    return int(lst[0])*60 + int(lst[1])

def minuteToTime (minute):
    div, mod = divmod(minute,60)
    return "%02d:%02d" % (div, mod)

def crewTime(timetable):
    return [timeToMinute(time) for time in timetable]

def shuttleTime(n, t, start = '09:00'):
    shuttle = [timeToMinute(start)]
    for n1 in range(n-1):
        shuttle.append(shuttle[-1]+t)
    return shuttle

def duplicateTime(c,integrate):
    if not c in integrate.keys():
        return c
    else:
        return duplicateTime(c + 0.001, integrate)

def solution(n, t, m, timetable):
    crew = sorted(crewTime(timetable))
    shuttle = shuttleTime(n, t)

    conTime = set(shuttle + crew)
    for c in set(crew):
        conTime.add(c - 1)
    for con in sorted(list(conTime))[::-1]:
        integrate = dict()
        for c in crew:
            integrate[duplicateTime(c,integrate)] = 'crew'
        integrate[duplicateTime(con,integrate)] = 'con'
        for sh in shuttle:
            integrate[duplicateTime(sh,integrate)] = 'shuttle'
        waiting_line = []
        for time in sorted(integrate.keys()):
            if 'crew' == integrate[time]:
                waiting_line.append('crew')
            elif 'con' == integrate[time]:
                waiting_line.append('con')
            elif 'shuttle' == integrate[time]:
                waiting_line = waiting_line[m:]
        if not 'con' in waiting_line:
            return minuteToTime(con)

백트래킹(Backtracking) 알고리즘을 이용한 풀이이다.

def timeToMinute (time):
    lst = time.split(':')
    return int(lst[0])*60 + int(lst[1])

def minuteToTime (minute):
    div, mod = divmod(minute,60)
    return "%02d:%02d" % (div, mod)

시간의 표현 형식은 최소한의 단위로 계산 하는 게 편하기 때문에 두 형식을 변환하는 함수를 각각 만들었다.

def shuttleTime(n, t, start = '09:00'):
    shuttle = [timeToMinute(start)]
    for n1 in range(n-1):
        shuttle.append(shuttle[-1]+t)
    return shuttle

셔틀이 오는 시간에 대한 리스트를 반환하는 함수도 하나 만들었다. 여기서 위에 만든 형식 변환 함수인 timeToMinute를 사용한다. 그리고 이제 본격적으로 문제로 들어가게 되는 데 셔틀 시간과 크루들의 시간을 합친 집합을 만들고, 추가적으로 가능 성이 있는 시간으로 해당 시간에 1분을 뺀 값을 집합에 추가해서 정답의 가능성을 가진 것들만 모인 콘의 시간이 될 conTime이라는 집합을 작성한다.

이 때, conTime을 시간이 큰 것부터 내림차순으로 확인하게 되면 콘이 버스를 못 타다가 처음으로 버스를 탈 수 있는 시간이 구해질 것이다. 그리고 이 시간이 바로 콘이 셔틀 버스를 탈 수 있는 제일 늦은 시간이 되게 된다.

내림차순으로 확인하다보면, crew의 시간이 겹치는 경우가 생기게 되는 데, 해당 문제풀이에 사용된 사전형의 경우 중복을 허용하지 않아 문제가 생긴다. 따라서 이를 파훼하기 위해 새로운 함수를 작성한다.

def duplicateTime(c,integrate):
    if not c in integrate.keys():
        return c
    else:
        return duplicateTime(c + 0.001, integrate)

인자로 integrate라는 딕셔너리 자료형에 넣을 key값(시간)과 현재 for-loop를 돌고 있는 integrate라는 딕셔너리 자료형을 넣고, 만일 시간 값이 현재 딕셔너리 자료형인 integrate에 있다면 재귀를 통해 0.001을 더하는 방식이다. 이렇게 코드를 짜게 되면, {540: 'crew', 540.001: 'crew', 540.002: 'crew', 540.0029999999999: 'crew', 541: 'con', 540.0039999999999: 'shuttle', 541.001: 'shuttle'} 이런 식으로 저장되어 그 안에서 중복을 피할 수 있다.

for time in sorted(integrate.keys()):
            if 'crew' == integrate[time]:
                waiting_line.append('crew')
            elif 'con' == integrate[time]:
                waiting_line.append('con')
            elif 'shuttle' == integrate[time]:
                waiting_line = waiting_line[m:]

그리고 integrate 딕셔너리 자료형을 이용해 waiting_line에 crew와 con을 넣어 줄을 만들고 shuttle이 오면 줄을 없에는 구조로 짠다. 결과적으로 waiting_line에는 해당 시행의 con 위치일 때, 버스를 못 탄 인원이 나오게 될 것 이다. 이제 waiting_line에 콘이 없다면 콘이 정상적으로 버스를 타게 된 가장 늦은 시간이라는 뜻이기 때문에 이를 반환하면 문제는 해결된다.

 if not 'con' in waiting_line:
            return minuteToTime(con)

👀 눈 여겨 볼 만한 풀이

def solution(n, t, m, timetable):
    answer = ''
    timetable = [ int(time[:2])*60 + int(time[3:5]) for time in timetable ]

    timetable.sort()

    for i in range(n):
        last_time = 540 + (n - 1) * t
        if len(timetable) < m:
            return '%02d:%02d' % (last_time // 60, last_time % 60)
        if i == n - 1:
            if timetable[0] > last_time:
                return '%02d:%02d' % (last_time // 60, last_time % 60)
            time = timetable[m - 1] - 1
            return '%02d:%02d' % (time // 60, time % 60)
        for j in range(m-1, -1, -1):
            bus_arrive = 540 + i * t
            if timetable[j] <= bus_arrive:
                del timetable[j]

이 풀이는 timetable을 지워가는 방식으로 풀었다.

첫 번째로 체크할 건 timetable의 길이가 m보다 작은가이다. 작은 경우 버스가 충분히 많은 경우로 버스의 마지막 시간이 답이 된다.

두 번째로 체크할 건 해당 시행이 마지막인 지에 대한 것이다. 남은 인원 중 시간이 가장 작은 timetable[0]가 버스 마지막 시간보다 커도 역시 버스의 마지막 시간이 답이 된다. 그렇지 않으면, 마지막에 버스에 타는 크루의 시간 보다 1이 작은 값을 반환하면 된다.

그리고 해당 버스 시간 이하에 해당하는 timetable에 해당하는 인원을 지우는 for-loop인데 여기서 한 가지 특이한 방식을 썼다. range(m-1, -1, -1)을 사용해서 0에서 m-1까지 에 해당하는 timetable을 비교하는 데 거꾸로 비교하면서 timetable을 지워갔다. 이 방식을 일반적인 range의 사용법처럼 range(0, m-1)로 하게 되면 인덱스가 적은 배열의 요소 부터 지우게 되므로 timetable이 원치 않은 결과 값을 갖게 된다. 일반적으로 for in loop에서 배열을 제거하는 행동은 하지 않는 데, 이렇게 하게 되면 for in loop를 이용하면서 원하는 리스트 값을 얻을 수 있게 된다.

cf. 문제 해석에 많은 시간이 들기 때문에, 나올 수 있는 경우의 수 최대한 빨리 나누는 게 이 문제의 핵심이다. 그렇게 하지 못한 다면 내 풀이 방법처럼 모든 가능성을 시험해보는 수 밖에 없다.