프로그래머스 코딩테스트 고득점 Kit_스택/큐_다리를 지나는 트럭

문제 보러 가기 👈 클릭!

💡 풀이

✔ 풀이 방법

트럭이 다리를 건너는데까지 걸리는 시간 = bridge_length 이므로
다리 위 트럭을 표현하는 큐에 [0]*bridge_length를 초기값으로 할당하고, 1초씩 지날때마다 popleft(), 다리위에 올라갈 트럭이 있으면 해당 트럭의 무게를 추가하고 아니면 0을 추가한다.

다리 위 트럭 무게의 합을 구할때, sum(trucks_on_bridge)를 사용할 수 있으나 시간복잡도가 n으로 크기 때문에 다리위에 트럭이 올라가거나 다리를 다 건널때마다 다리 위 트럭 무게의 합을 조정한다.

구현 코드 👇

#트럭이 다리를 건너는데까지 걸리는 시간 = bridge_length
from collections import deque
def solution(bridge_length, weight, truck_weights):
    truck_weights = deque(truck_weights) #큐 자료구조 사용
    trucks_on_bridge = deque([0] * bridge_length) #다리 위 트럭 list
    sec, sum_on_bridge = 0, 0 #시간, 다리 위 트럭 무게 합
    while trucks_on_bridge:
        sec += 1
        sum_on_bridge -= trucks_on_bridge.popleft()
        
        if truck_weights:
            if sum_on_bridge + truck_weights[0] <= weight:
                sum_on_bridge += truck_weights[0]
                trucks_on_bridge.append(truck_weights.popleft())
            else: 
                trucks_on_bridge.append(0)
    return sec