[프로그래머스] 다리를 지나가는 트럭

문제

트럭 여러 대가 순서대로 다리를 지나가야 한다. 단, 다리는 bridge_length 만큼의 길이를 가지며, 동시에 올라갈 수 있는 트럭의 무게 합은 weight를 넘지 않아야 한다. 트럭은 1초에 1만큼 이동, 다리에 올라간 순서대로 움직인다. 모든 트럭이 다리를 건너는 데 걸리는 최소 시간을 구해야한다.

---

풀이방법

풀이 시간 : 30분

풀이 방법 : 시뮬레이션 + 큐(Queue)

 

처음에는 단순히 다리 길이나 무게 제한만 고려해서 트럭을 올릴 수 있는지 판단하면 된다고 생각했다.

하지만 다리 위에서 트럭이 동시에 이동하고, 무게 제한도 유지하며 매 초마다 트럭이 한칸씩 이동한다는 점에서 단순 조건문으로는 해결할 수 없었따.

 

예를 들어,

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

이 경우,

• 처음 7이 올라가고 1초 뒤에는 다리 위에 있음
• 4는 바로 못 올라감 (7 + 4 > 10), 한 칸 대기
• 7이 다리를 빠질 때까지 기다려야 하고
• 이 시간 흐름을 모두 반영해줘야 한다.

따라서 매 초마다 트럭을 이동시키는 방식의 시뮬레이션이 필요하다고 판단했다.

 

구현은 아래와 같은 방식이다

1. bridge_length 크기의 큐를 사용하여 다리 위 상태를 시뮬레이션한다. (트럭이 지나가는 칸마다 1초씩 소요)
2. 매 초마다 큐에서 한 칸씩 트럭을 이동시키고, 나가는 트럭은 제거하며 무게를 빼준다.
3. 다음 트럭이 올라갈 수 있다면 큐에 넣고 무게를 더하고, 아니면 0을 넣어 시간을 흘려보낸다.
4. 모든 트럭이 다리에 진입하면, 마지막 트럭이 다리를 완전히 빠져나가는 시간인 bridge_length를 더한다.

시간	큐 상태	트럭 대기열	총 무게	설명
0	[0, 0]	[7, 4, 5, 6]	0	초기 상태
1	[0, 7]	[4, 5, 6]	7	7 진입
2	[7, 0]	[4, 5, 6]	7	1초 경과, 7 앞으로 이동
3	[0, 4]	[5, 6]	4	7 나감, 4 진입
4	[4, 5]	[6]	9	4 앞으로 이동, 5 진입
5	[5, 0]	[6]	5	4 나감, 5 앞으로 이동
6	[0, 6]	[]	6	5 나감, 6 진입
7	[6, 0]	[]	6	1초 경과, 6 앞으로 이동
8	[0, 0]	[]	0	6 나감, 종료

---

코드

import java.util.*;

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

        for (int i = 0; i < bridge_length; i++) {
            bridge.offer(0); // 다리 초기 상태
        }

        while (idx < truck_weights.length) {
            time++;
            totalWeight -= bridge.poll(); // 맨 앞 트럭 제거 (다리에서 나감)

            if (totalWeight + truck_weights[idx] <= weight) {
                bridge.offer(truck_weights[idx]);
                totalWeight += truck_weights[idx];
                idx++;
            } else {
                bridge.offer(0); // 새로운 트럭을 올릴 수 없으면 빈 공간 유지
            }
        }

        return time + bridge_length; // 마지막 트럭이 빠지는 시간 포함
    }
}