[스택/큐] 다리를 지나는 트럭 - Python / JavaScript

문제 링크 - https://school.programmers.co.kr/learn/courses/30/lessons/42583

프로그래머스

 

[문제 간단 요약]

1. 길이가 bridge_length인 다리를 트럭들이 들어간 순서대로 건너간다.
2. 다리 위 트럭 총 무게는 weight를 초과할 수 없다.
3. 매 초마다 트럭은 한 칸씩 전진하고, 다리 길이만큼 이동하면 빠져나온다.
4. 모든 트럭이 건너는 데 걸리는 총 시간을 구하는 문제.

 

[문제 해결 방안]

✅ 큐(Queue) 시뮬레이션 + 슬라이딩 창(bridge)

• 다리를 길이 bridge_length의 큐로 보고, 매 초마다 popleft()로 맨 앞을 빼서 다리에서 내려오는 트럭의 무게 차감
• 트럭을 올릴 수 있으면(현재 다리 무게 + 다음 트럭 ≤ weight) 트럭 무게를 append, 아니면 0을 append
• 대기 트럭 큐가 빌 때까지 시간을 누적하고, 마지막으로 다리 위에 남아 있는 트럭들이 빠져나가도록 bridge_length 초 더하

[문제 해결 코드 - python]

from collections import deque

def solution(bridge_length, weight, truck_weights):
    q = deque(truck_weights)
    bridge = deque([0] * bridge_length)
    time = 0
    current_weight = 0

    while q:
        time += 1
        current_weight -= bridge.popleft()

        if current_weight + q[0] <= weight:
            new_weight = q.popleft()
            current_weight += new_weight
            bridge.append(new_weight)
        else:
            bridge.append(0)

    return time + bridge_length

 

[문제 해결 코드 - JavaScript]

function solution(bridge_length, weight, truck_weights) {
  const waiting = [...truck_weights];
  const bridgeQueue = []; // { w: 트럭무게, exit: 내려오는 시각 }
  let time = 0;
  let onBridge = 0;

  while (waiting.length > 0 || onBridge > 0) {
    time += 1;

    // 내려올 차례면 내리기
    if (bridgeQueue.length && bridgeQueue[0].exit === time) {
      onBridge -= bridgeQueue[0].w;
      bridgeQueue.shift();
    }

    // 다음 트럭 올릴 수 있으면 올리기
    if (waiting.length && onBridge + waiting[0] <= weight && bridgeQueue.length < bridge_length) {
      const w = waiting.shift();
      onBridge += w;
      bridgeQueue.push({ w, exit: time + bridge_length });
    }
  }

  return time;
}