[프로그래머스] 다리를 지나는 트럭 - 42583(Java)

문제 URL

https://school.programmers.co.kr/learn/courses/30/lessons/42583

문제 설명

다리 위에서 트럭들이 일정 시간 동안 다리를 건너는 상황을 시뮬레이션하는 문제입니다. 트럭은 다리의 길이를 넘지 않도록 동시에 다리를 건널 수 없으며, 다리의 최대 하중을 초과하지 않도록 트럭이 건너야 합니다. 각 트럭은 다리의 길이를 한 칸씩 지나갈 때마다 1초가 지나고, 트럭이 다리를 건너는 데 걸리는 시간은 트럭이 다리를 전부 건넌 후에 다른 트럭이 진입할 수 있게 됩니다.

---

풀이

이 문제는 큐(Queue) 자료구조를 사용하여 각 트럭의 진행 상황을 관리하고, 시간과 다리 위의 무게를 계산하는 방식으로 해결할 수 있습니다.

1. 다리 위 상태 업데이트: 각 트럭은 다리 위에서 진행 중입니다. 다리 길이를 bridge_length로 지정하고, 다리 위에서 진행 중인 트럭들을 큐로 관리합니다.
2. 트럭 추가 조건 확인: 다리 위의 트럭들이 지나갈 때마다 그들의 무게를 빼고, 새로운 트럭이 들어갈 수 있는지 확인합니다.
3. 무게 초과 시 대기: 만약 다리의 총 하중이 초과하면, 대기 큐에 0을 추가하여 시간을 소모하고 대기합니다.
4. 결과 반환: 모든 트럭이 다리를 건넌 후 최종 시간을 반환합니다.

나의 풀이

import java.util.LinkedList;
import java.util.Queue;

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

        for (int truck : truck_weights) {
            while (true) {
                // ❶ 다리 위 상태 업데이트
                if (bridge.size() == bridge_length) {
                    totalWeight -= bridge.poll();  // 다리에서 나가는 트럭의 무게를 차감
                }

                // ❷ 트럭 추가 조건 확인
                if (totalWeight + truck <= weight) {
                    bridge.add(truck);  // 다리 위에 트럭을 추가
                    totalWeight += truck;  // 다리 위 총 무게 갱신
                    time++;  // 시간 증가
                    break;
                } else {
                    // 무게 초과 시 다리 길이를 유지하며 대기
                    bridge.add(0);  // 대기 중인 트럭은 0으로 표시
                    time++;  // 시간만 증가
                }
            }
        }

        // 모든 트럭이 다리를 건넌 후의 추가 시간
        return time + bridge_length;
    }
}

---

코드 실행 예

경과 시간	다리를 지난 트럭	다리를 건너는 트럭	대기 트럭
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]	[]	[]

1. 경과 시간 0: 트럭들이 대기 중이며, truck_weights = [7, 4, 5, 6]입니다.
2. 경과 시간 1~2: 첫 번째 트럭(7)이 다리를 건너고 다리 위에 올라갑니다. 이때 다리의 무게는 7입니다.
3. 경과 시간 3: 첫 번째 트럭(7)이 다리 끝에 다다르고, 다리 위에는 4만 남습니다.
4. 경과 시간 4: 두 번째 트럭(4)이 다리에 올라가고, 다리의 총 무게는 4입니다.
5. 경과 시간 5: 두 번째 트럭(4)이 다리 끝에 다다르고, 다리 위에는 5만 남습니다.
6. 경과 시간 6~7: 마지막 트럭(6)이 다리를 건너기 위해 올라가며, 대기 중인 트럭이 없어진 시점입니다.
7. 경과 시간 8: 모든 트럭이 다리를 건넌 후, 다리 위에서 아무도 남지 않게 됩니다.

---

결론

이 문제는 큐를 활용하여 트럭들이 다리를 건너는 시간을 효율적으로 관리할 수 있습니다. 각 트럭이 다리를 건너는 과정과 시간 흐름을 추적하면서 무게 조건을 고려하여 대기열을 관리하면 문제를 해결할 수 있습니다.