[programmers] 다리를 지나는 트럭 - Java

다리를 지나는 트럭

문제 설명

제한 조건

• bridge_length는 1 이상 10,000 이하입니다.

• weight는 1 이상 10,000 이하입니다.

• truck_weights의 길이는 1 이상 10,000 이하입니다.

• 모든 트럭의 무게는 1 이상 weight 이하입니다.

입출력 예

solution.java

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 currentWeight = 0;

        for (int truck : truck_weights) {
            while (true) {
                if (bridge.isEmpty()) {
                    // 다리가 비어 있으면 트럭이 건너기 시작
                    bridge.add(truck);
                    currentWeight += truck;
                    time++;
                    break;
                } else if (bridge.size() == bridge_length) {
                    // 다리를 지난 트럭을 제거
                    currentWeight -= bridge.poll();
                } else {
                    // 현재 트럭을 다리에 추가할 수 있는지 확인
                    if (currentWeight + truck <= weight) {
                        bridge.add(truck);
                        currentWeight += truck;
                        time++;
                        break;
                    } else {
                        // 시간의 흐름을 보여줄 placeholder를 추가
                        bridge.add(0);
                        time++;
                    }
                }
            }
        }

        // 마지막 트럭이 지나는데 필요한 시간인 남은 다리 길이를 추가
        return time + bridge_length;
    }
}

핵심 키워드

• 각 반복에서 다음과 같은 이유로 시간이 1초씩 증가한다.
• 다리에 트럭이 추가될 경우
• 또는 다리의 상태가 변경될 경우(트럭이 나가거나 placeholder가 추가됨).

• 매초마다 다음과 같은 일이 일어난다.
• 트럭은 다리에서 한 위치 앞으로 이동한다(대기열에서 제외되고 대기열에 추가됨).
• 다리가 최대 길이(bridge_length)에 도달하면 가장 오래된 트럭(또는 placeholder)이 제거된다.

• 시간 계산 방법은 다음과 같다.
• 무게 제한을 초과하지 않으면 트럭이 다리에 추가된다.
• 교량의 현재 중량이 용량을 초과하는 경우 트럭을 추가하지 않고 시간 경과를 시뮬레이션하기 위해 placeholder(0)가 추가됩니다.
• 모든 트럭 처리를 마치고 나서도 마지막 트럭이 다리를 완전히 건너려면 추가 시간이 필요하기 때문에 남은 다리 길이를 시간에 추가한다.

결론!