2018 KAKAO 코딩테스트 셔틀버스

https://programmers.co.kr/learn/courses/30/lessons/17678#

코딩테스트 연습 - [1차] 셔틀버스

 

 

겉 보기에는 구현 문제였다.

처음 생각한 벙법은 bus를 구성하고, 여기에서 여러 조건들을 고려하여 탑승시간을 찾는 방법이었다.

하지만, 나는 여러 조건들을 생각하는 것이 좀 힘들었다.

문제를 보니 탑승 시간이 00:00 ~ 23:59 로 한정되어 있고, 승객의 수가 2000명 이하여서 많이 Naive한 풀이가 가능하다고 생각했다. 그래서 모든 시간에 T에 대해서 T시간에 버스를 탄다 생각했을때, 탈 수 있냐 없냐를 확인하는 쪽으로 생각했다.
이때, 가장 늦게 탑승할 수 있는 시간을 구하는 것이니, 가장 늦은시간부터 탑승이 가능한지 확인하면 된다. 문제의 조건에 의해, 가장 늦게 탑승가능한 시간은 18:00이므로, 이때부터 확인하면 된다.

''' psudo code
for time in 18:00 ~ 00:00:
	if can_ride(time):
    	return answer
        
return 00:00
'''

 

여기서 시간을 좀 더 줄일 수 있는 방법은 time을 찾는 과정을 이진탐색으로 만들면 된다.

시간 T에 탑승이 가능한지 확인하는 방법은 현재 승객 정보(timetable)에 가상의 탑승시간 T를 넣은 timestamp를 기반으로 bus 를 구성하고, bus 안에 시간 T가 timestamp 안의 T의 개수와 같은지 확인하는 것이다. 왜냐하면, 콘은 같은 시간에 도착한 사람들 중에서는 가장 나중에 버스를 타기 때문이다.

내 생각대로 하면, 다음과 같은 코드가 나온다.

import bisect

def time_to_int(t):
    h,m = t.split(":")
    return int(h)*60+int(m)
def int_to_time(i):
    return "{0:02d}:{1:02d}".format(i//60,i%60)


def solution(n, t, m, timetable):
    
    last_bus_time = time_to_int("09:00") + (n-1)*t
    
    def search(time):
    
        timestamp = [time_to_int(e) for e in timetable if time_to_int(e) <= last_bus_time]
        timestamp.append(time)
        timestamp.sort()
    
        idx_bus = 0
        idx_cus = 0
        m_cnt   = 0
        bus = [[] for _ in range(n)]
        t_cnt   = 0
        
        while idx_cus < len(timestamp):
            now_bus_time = time_to_int("09:00") + idx_bus*t
            if idx_bus >= n: break
            if timestamp[idx_cus] <= now_bus_time and m_cnt < m:
                bus[idx_bus].append(timestamp[idx_cus])
                if(timestamp[idx_cus] == time):
                    t_cnt += 1
                idx_cus += 1
                m_cnt += 1
            else:
                m_cnt = 0
                idx_bus += 1

        if timestamp.count(time) == t_cnt:
            return True
        else:
            return False
        
    #개선점 : parametric search
    for i in range(last_bus_time, -1, -1):
        if search(i):
            return int_to_time(i)
        
            
    return None

 

만약, 탑승시간의 범위와 승객수가 더 크다면, 처음에 생각했던 것 처럼 구현할 것 같다. 하지만 같은 조건의 문제를 시험장에서 만난다면, 위와 같이 예외를 고려할 필요가 없는 코드를 짤 것 같다.