[프로그래머스][스택/큐] 다리를 지나는 트럭

내가 푼 풀이

from collections import deque
def solution(bridge_length, weight, truck_weights):
    #초기화
    answer = 0
    trucks_in_bridge = deque([])
    waiting_truck = deque([idx, truck_weight] for idx, truck_weight in enumerate(truck_weights))
    time = [0 for i in range(10001)]
    
    #1번 트럭 다리에 넣어주는 로직
    trucks_in_bridge.append([0, truck_weights[0]])
    waiting_truck.popleft()
    total = truck_weights[0]
    
    while trucks_in_bridge:
        cur = trucks_in_bridge[0]
        if time[cur[0]] >= bridge_length: #다리 다 건넘
            total -= cur[1]
            trucks_in_bridge.popleft()
        if waiting_truck:
            next = waiting_truck[0]
            if total + next[1] <= weight: #새로운 트럭 들어옴
                total += next[1]
                trucks_in_bridge.append(next)
                waiting_truck.popleft()
        for truck in trucks_in_bridge: #1초 경과
            time[truck[0]] += 1
        answer += 1 
    return answer

문제 이해하는데 시간이 꽤 걸렸고, 시간을 카운트할 때가 약간 헷갈려서 소요 시간이 조금 있었던 문제다.

문제를 풀이하자면, bridge_length만큼의 길이를 갖는 다리가 있다. 트럭은 1초에 1만큼 움직일 수 있다(이런 말이 따로 없어서 예제를 보고 이해했다 ㅠ). 다리는 일차선이며 weight 무게만큼 버틸 수 있다. 다리를 건너는 트럭의 순서와 무게는 truck_weights로 주어진다.

다리는 일방통행이기 때문에 선입선출이므로 이 문제는 queue로 해결할 수 있다. 다리에 올라와있는 트럭을 trucks_in_bridge라는 큐로 관리했고, waiting_truck을 이용해 대기중인 트럭을 하나씩 빼서 trucks_in_bridge에 넣어줬다. time이라는 리스트를 통해 트럭 하나하나가 다리에서 보낸 시간을 세서 bridge_length보다 커질 때 다리를 건넌 것으로 취급, pop해주었다. 트럭을 pop하는 로직 이후, 새로운 트럭이 들어올 수 있는지 전체 무게 정보를 갖고있는 total이라는 변수를 통해 확인하고, 들어올 수 있으면 append해주었다.

번외(초기화 방법)

C++에 익숙해져서, 배열 크기를 선언을 안하니깐 굉장히 어색했다. 그리고 리스트도 특정 크기만큼 값이 없으면, out of bound를 내뱉는다. 그래서 찾은 초기화 방법은

time = [0 for i in range(10001)]

이렇게 최대 크기만큼 리스트를 초기화해주는 것이다. 생각보다 별거 없네 ..