[프로그래머스] 다리를 지나는 트럭 (Java) — 스택과 큐

📌 핵심 요약

• 다리를 "큐"로 보면 끝난다 — 다리 길이만큼 0으로 채운 큐를 매 초 한 칸씩 밀어내는 시뮬레이션이다.
• 매 초 흐름은 딱 두 가지 — ① 맨 앞 칸 빼기 → ② 트럭을 올릴 수 있으면 올리고, 아니면 0(빈 칸)을 채운다.
• total 변수로 무게를 들고 다닌다 — 매번 큐를 다 더하지 않고 다리 위 총 무게를 O(1)로 확인한다.

 

 

목차

 

1 문제

트럭 여러 대가 일렬로 다리를 건넌다.

다리는 길이가 bridge_length이고, 동시에 올라온 트럭들의 무게 합이 weight를 넘으면 안 된다. 트럭은 순서를 지켜 한 대씩 올라가고, 모든 트럭이 다리를 완전히 건너는 데 걸리는 최소 시간(초)을 구하는 문제다.

Programmers #42583

다리를 지나는 트럭

다리 길이 · 무게 · 트럭 수 ≤ 10,000

난이도: Lv.2

트럭이 다리를 1초에 한 칸씩 이동한다. 다리에 올라온 트럭들의 무게 합이 항상 제한 무게 이하여야 하고, 트럭은 입력 순서대로만 올라갈 수 있다. 모든 트럭이 다리를 빠져나가는 순간까지의 시간을 반환한다.

풀이 한 줄 요약

1. 다리를 길이 고정 큐로 만들고, 매 초 맨 앞을 빼면서 뒤에 트럭(또는 빈 칸)을 채워 넣는다.
2. 모든 트럭이 올라간 시점에서 다리 길이만큼을 더하면 완전 통과 시간이다.

2 다리를 큐로 바라보기

처음엔 "1초에 한 칸씩 움직인다"를 코드로 어떻게 옮길지 막막했다.

트럭마다 현재 위치를 따로 들고 다닐까 싶었는데, 생각해 보니 그럴 필요가 없었다. 다리 자체를 큐로 보면 깔끔하게 풀린다.

큐 한 칸 = 다리 한 칸 = 1초

다리 길이가 곧 큐의 크기다. 큐 안의 칸 하나하나가 다리 위의 한 위치이고, 큐를 한 번 밀어내는 게 곧 1초가 흐르는 것과 같다. 트럭이 없는 빈 자리는 0으로 표현했다.

그래서 매 초 하는 일은 단순하다. 맨 앞 칸을 poll로 빼내고(그 칸이 다리를 빠져나감), 뒤에는 새 트럭을 add하거나 더 못 올릴 상황이면 0을 채운다.

큐 크기가 항상 다리 길이로 유지되니까 "한 번 밀면 1초"가 자연스럽게 성립한다.

💡

total 변수를 따로 둔 이유

무게 제한을 확인하려면 다리 위 트럭들의 합이 필요한데, 매번 큐를 전부 더하면 그 자체가 O(다리 길이)다. 그래서 다리 위 총 무게를 total이라는 변수에 들고 다니면서, 칸을 뺄 때 빼고 트럭을 올릴 때 더하는 식으로 항상 최신 합을 O(1)에 알 수 있게 했다. "필요할 때마다 다시 세지 말고, 변할 때마다 갱신해서 들고 다닌다"는 패턴이다.

3 풀이 코드

아이디어가 잡히면 코드는 거의 그대로 옮겨진다. 흐름이 한눈에 보이도록 단계별 번호 주석을 달아 뒀다.

   

Java — Solution.java

import java.util.*;

class Solution {
    public int solution(int bridge_length, int weight, int[] truck_weights) {
        int answer = 0;
        Queue<Integer> bridge = new LinkedList<>();

        // ① 다리 길이만큼 0(빈 칸)으로 큐를 채워 둔다
        for (int i = 0; i < bridge_length; i++) {
            bridge.add(0);
        }

        int total     = 0;   // 다리 위 트럭들의 총 무게
        int truck_idx = 0;   // 다음에 올릴 트럭 인덱스

        // ② 모든 트럭이 다리에 올라갈 때까지 반복
        while (truck_idx < truck_weights.length) {
            answer++;                      // 1초 경과
            total -= bridge.poll();  // 맨 앞 칸을 빼낸다(다리에서 빠져나감)

            // ③ 다음 트럭을 올려도 제한 무게를 넘지 않으면 올린다
            if (total + truck_weights[truck_idx] <= weight) {
                bridge.add(truck_weights[truck_idx]); // 트럭 올리기
                total += truck_weights[truck_idx];    // 총 무게 갱신
                truck_idx++;                            // 다음 트럭으로
            } else {
                bridge.add(0);    // 못 올리니 빈 칸을 채운다
            }
        }

        // ④ 마지막 트럭이 올라간 순간 → 다리 길이만큼 더 가야 완전 통과
        answer += bridge_length;

        return answer;
    }
}

while문이 멈추는 순간

반복 조건이 truck_idx < truck_weights.length인 점이 포인트다.

마지막 트럭을 다리에 올리는 순간 truck_idx가 트럭 개수와 같아져서 while문이 끝난다.

즉 이때의 answer는 "마지막 트럭이 다리에 막 올라간 시각"일 뿐, 아직 건너지는 못한 상태다.

그래서 마지막에 다리 길이만큼을 더해야 그 트럭이 완전히 빠져나가는 시각이 된다.

4 예제

말로만 보면 헷갈리니 bridge_length=2, weight=10, truck_weights=[7,4,5,6]를 직접 한 초씩 따라가 봤다.

다리 상태는 [앞칸, 뒤칸] 순서다.

초(answer)	빠진 칸	올린 트럭	다리 상태	total
1	0	7 탑승	[0, 7]	7
2	0	4 대기	[7, 0]	7
3	7	4 탑승	[0, 4]	4
4	0	5 탑승	[4, 5]	9
5	4	6 대기	[5, 0]	5
6	5	6 탑승	[0, 6]	6

6초에 마지막 트럭(6)이 올라가면서 while문이 끝난다. 여기에 다리 길이 2를 더하면 6 + 2 = 8. 예제 정답과 정확히 맞는다.

⚠️

마지막 +bridge_length 빼먹지 말기

가장 흔한 실수 두 개. ① while이 끝나면 답이 나온 줄 알고 그대로 반환하기 — 마지막 트럭이 아직 다리 위에 있다. ② 무게 비교를 <=가 아니라 <로 쓰기 — 무게가 딱 제한과 같을 때도 올라갈 수 있으므로 <=가 맞다.

5 시간복잡도와 마무리

while문은 전체 걸린 시간(초)만큼 돈다. 트럭 한 대가 다리에 오르는 데 최악의 경우 다리 길이만큼 기다리므로, 전체 반복 횟수는 대략 트럭 수 × 다리 길이에 비례한다.

각 반복 안에서 poll·add·total 갱신은 전부 O(1)이라 충분히 빠르다.

항목	복잡도	비고
시간	O(트럭 수 × 다리 길이)	각 초마다 O(1) 작업
공간	O(다리 길이)	큐 크기 = 다리 길이 고정

ℹ️

정리

"다리를 큐로 본다"는 관점 하나만 잡으면 나머지는 시뮬레이션을 그대로 옮기는 일이다. 트럭 위치를 일일이 추적하지 않고, 큐를 미는 행위에 시간 개념을 녹여 넣은 게 이 풀이의 핵심이다. total을 변수로 들고 다닌 것처럼, 매번 다시 계산하기보다 변할 때 갱신하는 습관이 큐·스택류 문제에서 두루 쓸모가 많다.

잘못된 내용이 있다면 지적부탁드립니다. 방문해주셔서 감사합니다.