[programmers/python] 다리를 지나는 트럭 - deque

1. 문제 개요

- url : https://school.programmers.co.kr/learn/courses/30/lessons/42583#

 

트럭이 여러 대 줄지어 대기 중이다. 다리의 길이는 bridge_length이며, 다리가 견딜 수 있는 최대 무게는 weight이다. 각 트럭의 무게는 truck_weights 배열에 순서대로 주어진다.

트럭은 순서대로만 다리에 올라갈 수 있고, 다리 위에서는 최대 bridge_length만큼의 트럭만 이동할 수 있다. 모든 트럭이 다리를 건널 때까지 걸린 최소 시간을 구해야 한다.

---

2. 핵심 아이디어

문제의 핵심은 트럭의 실제 위치와 다리 위의 무게를 함께 관리하는 것이다. 단순히 다리 위에 트럭 수만 세거나, 무게만 추적하면 순서와 시간 조건을 만족하기 어렵다.

핵심 전략:

• deque 큐를 사용해 다리 위 트럭 상태를 저장한다.
  각 트럭은 (무게, 남은 이동 거리) 형태로 관리한다.
• 매초마다:
  1. 모든 트럭의 남은 거리를 1씩 줄인다.
  2. 다리를 다 건넌 트럭(남은 거리 = 0)은 큐에서 제거한다.
  3. 대기 트럭을 순서대로 확인해, 무게와 다리 길이 조건을 만족하면 큐에 추가한다.
• 마지막 트럭이 다리를 완전히 다 건널 때까지 루프를 반복한다.

---

3. 최종 코드

from collections import deque

def solution(bridge_length, weight, truck_weights):
    time = 0
    bridge = deque()  # (트럭 무게, 남은 거리)
    total_weight = 0
    truck_weights = deque(truck_weights)
    
    while truck_weights or bridge:
        time += 1

        # 1) 다리 위 트럭 한 칸씩 이동
        if bridge and bridge[0][1] == 1:
            w, _ = bridge.popleft()
            total_weight -= w
        bridge = deque([(w, d-1) for (w, d) in bridge])
        
        # 2) 새로운 트럭을 올릴 수 있으면 추가
        if truck_weights:
            if total_weight + truck_weights[0] <= weight and len(bridge) < bridge_length:
                w = truck_weights.popleft()
                bridge.append((w, bridge_length))
                total_weight += w
    
    return time

---

 

• 다리 위 상태:
  bridge 큐에는 (트럭 무게, 남은 거리) 쌍이 저장된다. 예를 들어 (7, 2)는 무게 7의 트럭이 다리에서 앞으로 2초 남았다는 뜻이다.
• 다리 위 무게 계산:
  total_weight 변수를 따로 두어, 매번 다리 위 모든 트럭 무게를 sum()으로 다시 계산하지 않아도 된다.
• 다리 위 트럭 이동:
  매 루프마다 다리 위 트럭의 남은 거리 d를 1씩 줄이고, 다리 끝에 도달한 트럭은 popleft()로 제거한다.
• 새로운 트럭의 진입:
  대기 중인 트럭의 첫 번째 트럭만 고려한다. 다리 위 총 무게와 다리 길이를 만족하면 트럭을 올린다.