[Algorithm: 큐] 프로그래머스 <다리를 지나는 트럭>

스택/큐 시뮬레이션 Java Programmers Lv.2

문제

https://school.programmers.co.kr/learn/courses/30/lessons/42583?language=java

프로그래머스

 

---

 

문제 설명

일차선 다리에 트럭이 순서대로 진입한다. 다리는 최대 bridge_length대의 트럭을 수용하고, 무게 합이 weight를 초과하면 안 된다. 모든 트럭이 다리를 건너는 데 걸리는 최소 시간을 구하는 문제다.

경과 시간	다리를 지난 트럭	다리 위	대기
0	[]	[]	[7,4,5,6]
1~2	[]	[7]	[4,5,6]
3	[7]	[4]	[5,6]
4	[7]	[4,5]	[6]
5	[7,4]	[5]	[6]
6~7	[7,4,5]	[6]	[]
8	[7,4,5,6]	[]	[]

 

 

---

 

핵심 아이디어: 다리를 고정 길이 큐로 모델링

이 문제의 핵심은 다리를 길이가 고정된 큐로 표현하는 것이다. 매 초마다 큐의 앞에서 하나를 빼고 뒤에서 하나를 넣으면 다리 위 상황이 자연스럽게 시뮬레이션된다.

트럭이 없는 빈 칸을 0으로 채운다.
다리는 항상 bridge_length만큼의 슬롯을 가진다.
트럭이 진입하지 못할 때 0을 넣어 슬롯을 채워야 다리 길이가 유지되고 시간 흐름이 정확해진다.

bridge_length=2, weight=10, 트럭=[7,4,5,6]

초기 (t=0) 다리 비어있음 currentWeight=0

t=1 진입 7 0 ←진행 4 5 6 currentWeight=7

t=2 대기 7 0 ←진행 4 5 6 7+4=11 > 10 → 0 삽입

t=3 진입 4 7→빠짐 ←진행 5 6 currentWeight=4

t=4 진입 5 4 ←진행 6 4+5=9 ≤ 10 → 진입

0을 삽입하는 이유
트럭이 진입하지 못할 때도 시간은 1초 흐른다. 빈 슬롯을 0으로 채워야 다리 앞쪽 트럭이 1칸씩 정확히 전진하고, bridge_length 이후 다리를 벗어나게 된다. 0을 넣지 않으면 다리 길이가 줄어들어 트럭이 실제보다 빨리 건너는 오류가 생긴다.

 

종료 조건: while 루프를 언제 끝내는가

루프의 종료 조건이 조금 특별하다.

while (!waiting.isEmpty() || currentWeight > 0) {

두 조건을 OR로 연결하는 이유:
waiting이 비어도 마지막 트럭이 다리를 완전히 건너는 데 시간이 더 필요하다.
currentWeight > 0은 다리 위에 트럭이 남아있다는 뜻이므로, 이 조건까지 반복해야 모든 트럭이 다리를 완전히 건넌다.

 

 

매 초마다 동작 흐름

1

answer++ — 1초가 흘렀다

2

다리가 가득 찼으면(bridge.size() == bridge_length) 맨 앞 값을 poll()해서 currentWeight에서 뺀다

3

다음 트럭을 올려도 무게 제한을 넘지 않으면 진입, 넘으면 0을 삽입해 빈 슬롯 유지

전체 시뮬레이션 — [7,4,5,6], bridge_length=2, weight=10

t=1 70 대기[4,5,6] / cW=7

t=2 07 7+4=11 > 10 → 0 삽입 / 대기[4,5,6] / cW=7

t=3 4 (0 빠짐) 4+5=9 ≤ 10 → 4 진입 / 대기[5,6] / cW=4

t=4 54 4+5=9, 5 진입 / 대기[6] / cW=9

t=5 05 (4 빠짐) 5+6=11 > 10 → 0 삽입 / 대기[6] / cW=5

t=6 6 (0 빠짐) 6 진입 / 대기[] / cW=6

t=7 06 (0 빠짐) 대기[] / cW=6

t=8 종료 (6 빠짐) cW=0 → 루프 종료

answer = 8

 

 

---

 

최종 코드

import java.util.*;

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

        for (int w : truck_weights) waiting.offer(w);

        // 대기 트럭이 남았거나, 다리 위에 트럭이 있으면 계속
        while (!waiting.isEmpty() || currentWeight > 0) {
            answer++;

            // 1. 다리가 꽉 찼으면 맨 앞 제거
            if (bridge.size() == bridge_length) {
                currentWeight -= bridge.poll();
            }

            // 2. 다음 트럭 진입 가능하면 진입, 아니면 빈 슬롯(0) 삽입
            if (!waiting.isEmpty() && currentWeight + waiting.peek() <= weight) {
                int truck = waiting.poll();
                bridge.offer(truck);
                currentWeight += truck;
            } else {
                bridge.offer(0);   // 빈 슬롯으로 시간 흐름 유지
            }
        }

        return answer;
    }
}

 

 

---

정리

다리 = 고정 길이 큐

bridge를 큐로 모델링. 매 초 앞에서 poll, 뒤에서 offer해 1칸씩 전진을 표현.

0 삽입의 역할

트럭이 못 들어올 때 빈 슬롯을 0으로 채워 다리 길이와 시간 흐름을 정확히 유지.

currentWeight

다리 위 무게 합을 별도로 추적. poll 시 빼고 offer 시 더해 매번 큐 합산을 피함.

종료 조건

waiting이 비어도 currentWeight > 0이면 계속. 마지막 트럭이 다리를 완전히 건널 때까지.

이 문제의 핵심은 다리를 큐로 추상화하는 발상이다.
물리적인 다리의 "밀려나감"을 poll/offer로 자연스럽게 표현하고,
빈 슬롯을 0으로 채우는 방법으로 시간 흐름과 다리 길이를 동시에 관리한다.

 

 

 

* 이 포스팅은 Claude AI의 도움을 받아서 작성되었습니다.