• 코드
  • 핵심

다리를 지나는 트럭

코드

from collections import deque
def solution(bridge_length, weight, truck_weights):
    bridge = deque(0 for _ in range(bridge_length))
    total_weight = 0
    step = 0
    truck_weights.reverse()

    while truck_weights:
        total_weight -= bridge.popleft()
        if total_weight + truck_weights[-1] > weight:
            bridge.append(0)
        else:
            truck = truck_weights.pop()
            bridge.append(truck)
            total_weight += truck
        step += 1

    step += bridge_length

    return step

핵심

1. 다리는 deque로 표현된다. 다리 길이에 해당하는 0으로 채워진 deque를 생성한다.
2. total_weight는 현재 다리 위의 트럭 무게의 총합을 나타낸다.
3. truck_weights 리스트를 뒤집어, 트럭을 리스트의 마지막부터 처리한다. 이렇게 하는 것은 리스트의 끝에서 pop 연산이 O(1)의 시간 복잡도를 가지기 때문이다.
4. 모든 트럭이 다리를 건널 때까지 다음 과정을 반복한다:
   • total_weight에서 bridge의 첫 번째 요소(다리를 떠나는 트럭의 무게)를 빼고, 해당 트럭을 deque에서 제거한다.
   • 다리에 새 트럭이 올라갈 수 있는지 검사한다. 가능하다면, truck_weights에서 새 트럭을 꺼내 total_weight에 추가하고, deque에 트럭을 추가한다. 불가능하다면, deque에 0을 추가한다.
   • 각 단계마다 step을 1씩 증가시켜 시간을 계산한다.
5. 마지막으로, 모든 트럭이 다리를 건넌 후, 마지막 트럭이 다리를 완전히 벗어나는 시간(=bridge_length)을 step에 추가한다.