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

programmers.co.kr/learn/courses/30/lessons/42583

코딩테스트 연습 - 다리를 지나는 트럭

해결 아이디어

문제롤 보면 트럭 하나가 지나가는데 걸리는 시간은 다리의 길이 + 1 초이다.

 

• 큐에다가 트럭이 들어오지 않으면 0을 넣고 트럭이 들어오면 트럭의 무게를 넣어준다.
• 첫번째 트럭의 경우만 생각해보면 [ 0, 0, 7 ] 로 큐의길이인 3초만에 다리를 건너게 된다.
• 위와 똑같은 방법으로 다리의 길이만큼 따로 버퍼큐를 하나 빼서 다리의 현재 무게를 측정한다.
• 다리에 트럭이 진입가능하면 트럭의 무게만큼 큐에 추가하고 아니면 0을 추가한다

from collections import deque
def solution(bridge_length, weight, truck_weights):
    answer = 0
    q = deque()
    maxWeight = weight
    truck_on_bridge = deque()
    wait = deque(truck_weights)
    for i in range(bridge_length):
        q.append(0)               # 다리를 지나는 트럭을 추적하는 큐
        truck_on_bridge.append(0) # 현재 다리 무게를 측정하는 버퍼큐
    weightOnBridge = 0
    while wait:
        weightOnBridge-= truck_on_bridge.popleft()
        if maxWeight - weightOnBridge - wait[0]>=0:  # 진입 가능하면 트럭을 넣어줌
            q.append(wait[0])
            truck_on_bridge.append(wait[0]) # 다리무게 측정하는 버퍼큐에도 같은방식 사용
            weightOnBridge += wait[0]
            wait.popleft()
        else:                        # 트럭이 다리에 진입 불가능하면 0을 넣어줌
            q.append(0)
            truck_on_bridge.append(0) # 현재 다리무게를 측정하는 버퍼큐에도 같은방식 사용
        
    
    answer = len(q) # 트럭을 추적하는 큐의 길이가 답이 된다.
    
    return answer