[PRO] 다리를 지나는 트럭 | Python

문제

프로그래머스 코딩테스트 연습 > 스택/큐 > 다리를 지나는 트럭https://school.programmers.co.kr/learn/courses/30/lessons/42583

프로그래머스

 

 

 

 

 

풀이 과정

파이썬 풀이

from collections import deque

def solution(bridge_length, weight, truck_weights):
    answer = 0
    truck = deque(truck_weights)
    bridge = deque([0] * bridge_length)
    w = 0   # bridge위의 무게
    
    while bridge:
        answer += 1
        w -= bridge.popleft()
        
        if truck:
            # 무게 초과 안하면 truck[0] 다리 건너기
            if w + truck[0] <= weight:
                t = truck.popleft()
                bridge.append(t)
                w += t
            # 무게 초과시 못 건너니까 0을 추가
            else:
                bridge.append(0)
    return answer

• truck과 bridge 모두 앞에 있는 게 먼저 나가야 하므로 FIFO의 deque 사용
• 1초마다 다리의 가장 앞에 있는 트럭을 popleft()해서 없애고, 다리 위 트럭의 무게 합인 w에서 뺀다.
• 추가로 다리를 건널 수 있으면 대기 중인 트럭 중 하나를 bridge에 추가하고, w에 더해준다.
• 만약 대기 중인 트럭은 있으나 무게 초과로 건너지 못한다면 다음에 건너기 위해 0을 추가
• 만약 대기 중 트럭이 없으면 bridge에 추가하는 게 없기 때문에 bridge 위의 트럭이 다 지나갈 때까지만 while문 동작