프로그래머스 - 다리를 지나는 트럭

문제 설명

다리의 길이와 무게 제한이 주어질 때, 대기 중인 트럭이 모두 다리를 건너는 데 걸리는 최소 시간을 구하는 문제이다.

매 초마다 트럭은 한 칸씩 이동하며, 다리 위 트럭들의 무게 합이 제한을 초과하면 다음 트럭은 진입할 수 없다.

---

접근 방법

1. 다리는 길이가 있어서 한번에 올라갈 수 있는 트럭 수가 제한된다.
2. 다리는 무게 제한이 있어서 동시에 올라간 트럭의 무게 합이 제한을 넘으면 안 된다.
3. 매 초마다 트럭이 한 칸씩 이동한다.

먼저 들어간 트럭이 먼저 나오는 선입선출방식이다. 그러므로 다리를 Queue로 표현할 수 있다. 다리 위 빈 칸은 0으로 채우고, 매 초마다 앞에서 하나를 빼고 뒤에서 하나를 추가할수 있다.

다리 길이 = 3, 무게 제한 = 10
트럭 무게 = [7, 4, 5, 6]

초기 상태 → 다리: [0, 0, 0]

1초 후  → 다리: [0, 0, 7]   트럭 7 진입
2초 후  → 다리: [0, 7, 0]   트럭 4는 진입 불가 (7+4 > 10)
3초 후  → 다리: [7, 0, 0]
4초 후  → 다리: [0, 0, 4]   트럭 7 빠지고 트럭 4 진입
...

구체적으로 정리한 풀이 흐름:

1. 다리를 Queue로 초기화하고 빈 칸은 0으로 채우기

2. 매 초마다 poll()로 앞에서 하나 제거

3. 현재 다리 무게합 + 다음 트럭 무게 ≤ 무게 제한이면 다음 트럭이 진입(offer(truck_weights[idx]))

4. 조건 미충족이면 빈 칸 추가(offer(0))

5. 모든 트럭이 다리에 올라간 후 마지막 트럭이 완전히 건너는 시간 + bridge_length 추가

   while이 끝나는 시점은 마지막 트럭이 다리에 올라간 순간이지, 다리를 완전히 건넌 순간이 아니다. 마지막에 return time + bridge_length로 나머지 시간을 더해줘야 한다.

---

최종 코드

import java.util.*;

class Solution {
    public int solution(int bridge_length, int weight, int[] truck_weights) {
        Queue<Integer> bridge = new LinkedList<>();
        
        for (int i = 0; i < bridge_length; i++) {
            bridge.offer(0);
        }
        
        int time = 0;
        int idx = 0;
        
        while (idx < truck_weights.length) {
            bridge.poll();
            
            if (bridge.stream().mapToInt(i->i).sum() + truck_weights[idx] <= weight) {
                bridge.offer(truck_weights[idx]);
                idx++;
            } else {
                bridge.offer(0);
            }
            
            time++;
        }
        
        return time + bridge_length;
    }
}

---