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

문제 소개

오늘 풀었던 프로그래머스 - 다리를 지나는 트럭 문제를 정리합니다.

이 문제는 여러 트럭이 무게 제한과 길이 제한이 있는 다리를 지나가는 상황에서, 모든 트럭이 다리를 건너는 데 걸리는 최소 시간을 계산하는 문제입니다.

문제 링크: 다리를 지나는 트럭 - 프로그래머스

---

문제 접근 방식

이 문제는 다음과 같은 시뮬레이션으로 해결할 수 있습니다:

1. 다리를 bridge_length 길이의 큐로 구현
2. 매초마다 큐를 한 칸 밀고, 새로운 트럭을 올릴지 결정
3. 올릴 수 있는 조건:
   • 큐의 합 + 대기 중인 트럭 무게 ≤ weight
4. 큐의 맨 앞 요소는 다리를 지난 트럭 (무게를 빼야 함)
5. 모든 트럭이 지나갈 때까지 시간 증가시켜가며 반복

---

해결 과정 및 코드

핵심 아이디어

1. 다리를 무게 제한이 있는 슬라이딩 큐로 보고,
2. 매초마다 트럭을 한 칸씩 전진시키는 방식
3. 트럭을 못 올리는 경우에도 다리를 빈칸(0)으로 채워야 함

코드

시간 복잡도 : O(N)

import java.util.*;
class Solution {
    public static int solution(int bridge_length, int weight, int[] truck_weights) {
        ArrayDeque<Integer> bridge = new ArrayDeque<>();
        int time = 0;
        int totalWeight = 0;
        int i = 0;

        // 초기 다리 상태: 0으로 채움
        for (int j = 0; j < bridge_length; j++) {
            bridge.offer(0);
        }

        while (!bridge.isEmpty()) {
            time++; // 1초 경과
            totalWeight -= bridge.poll(); // 한 칸 앞으로 이동하며 맨 앞 트럭 제거

            if (i < truck_weights.length) {
                if (totalWeight + truck_weights[i] <= weight) {
                    bridge.offer(truck_weights[i]);
                    totalWeight += truck_weights[i];
                    i++; // 다음 트럭으로 이동
                } else {
                    bridge.offer(0); // 트럭을 못 올리는 경우 빈 공간 (0) 추가
                }
            }
        }

        return time;
    }
}