LV3 [KAKAO] [1차] 셔틀버스

---

문제

https://school.programmers.co.kr/learn/courses/30/lessons/17678?language=python3 

프로그래머스

 

풀이

이 문제의 요점은, 콘이 언제와야 '마지막 버스' 를 탑승할 것인가 이다.

 

마지막 버스에 한자리라도 남아있다면 마지막 버스시간에 오면 되고,

마지막 버스에 사람이 꽉 차 있다면 마지막 버스에, 마지막에 탄 사람 -1 분에 도착하면 된다.

 

 

 

처음에는 마지막 버스라는거에 꽂혀 "뒤에서 부터 살펴봐야하나?" 했는데 애초에 수가 크지도 않고, 크루가 얼마나 일찍 도착할지 모르기에 앞에서부터 버스에 태우면서 검사해보면 된다.

 

배차간격에 맞게 버스 리스트를 선언해주고, 일찍 도착한 순으로 크루를 정렬해준다.

 

다음에 버스를 앞에서부터 선정하여, 해당 버스보다 일찍 도착한 크루를 순서대로 채운다.

만약 버스가 가득찼거나, 버스보다 뒤늦게 도착한 크루라면 다음 버스로 넘어가서 이 과정을 반복한다.

 

중요한건 시간을 어떻게 효율적으로 비교하냐인데, 시간을 모두 분으로 환산한다음 비교하면 된다.

시간을 비교하는 문제가 나오면 하나의 수로 변환해서 푸는 방법을 항상 생각하자.

 

그렇게 마지막 버스까지 과정을 끝냈을 때, 위에서 말한대로

마지막 버스에 자리가 있다면 마지막 버스 도착시간에 맞춰 오면 되고, 마지막 버스가 꽉 찼다면 마지막 버스에 마지막에 탄 크루 보다 1분 일찍 오면 된다.

 

코드

def transform(time_str):
    h, m = time_str.split(':')
    return int(h)*60 + int(m)

def restore(time_int):
    h = str(time_int//60)
    m = str(time_int%60)
    
    if len(h) == 1: h = '0' + h
    if len(m) == 1: m = '0' + m

    return h+':'+m
    
def solution(n, t, m, timetable):
    busList = []
    # 9시부터 t분 간격으로 n개의 셔틀이 도착하며, m명을 태울 수 있다.
    for i in range(n):
        val = transform("09:00") + (t*i)
        busList.append(val)
    
    transCrew = [transform(crew) for crew in timetable]
    transCrew.sort()

    crewIdx = 0
    # 버스를 하나씩 돌면서 사람을 채운다.
    for i in range(len(busList)):
        temp = []
        cnt = 0
        while True:
            if crewIdx >= len(transCrew): break # 사람이 모두 탄 경우
            if cnt == m: break #버스에 정원이 모두 찼다면
            
            # 해당 버스보다 빨리 왔다면 태운다.
            if transCrew[crewIdx] <= busList[i]:
                temp.append(transCrew[crewIdx])
                cnt +=1
                crewIdx +=1
                
            # 해당 버스보다 늦게 왔다면 다음 버스로 넘어간다.
            else:
                break
            
        # 이게 마지막 버스였다면
        if i == len(busList)-1:
            # 그 버스가 만차라면, 그 버스를 마지막에 탄 사람 -1분에 오면 된다.
            if len(temp) == m: 
                return restore(temp[-1]-1)
            # 만약 한자리라도 비어있다면 버스가 도착하는 시간에 오면 된다.
            else: 
                return restore(busList[-1])

 

후기

 

2018년도 문제였고 공식해설을 보니 난이도는 [중] 이었다. 이게 레벨3인지도 의문이지만 카카오의 예전 난이도는 좀 인간적이었던 거 같다. 요새는 [하] 로 나올거 같은 ..