[Java] 다리를 지나는 트럭

정석·2024년 5월 6일

Java

알고리즘 학습

목록 보기

28/67

🧑🏻‍💻문제

💡문제 분석 요약

문제를 이해하는데 너무 오랜 시간이 걸렸고, 다리를 건너는 시간에 대해 이해를 못하고 있던 중에 다른 사람의 풀이를 보고 이해할 수 있었다. 참고

다리 위에서 한 칸씩 움직일 때마다 1초가 흐른다. 만약 다리의 길이가 2라면 한 트럭이 지나갈 때까진 2초의 시간이 흐르게 된다. 다리에 올라갈 수 있는 트럭의 무게는 제한이 있고, 무게 제한을 넘지 않는 선에서 트럭을 움직인다.

💡알고리즘 설계

생각해야 할 조건들이 되게 많은데 나열해보자면 아래와 같다.

1. 다리가 비어있을 경우

트럭을 다리에 올림 (다리 큐에 넣는다)
다리 위의 무게 계산을 위해 sum 값에 저장
다리에 트럭이 한 칸 들어왔으니 시간을 1 더한다

2. 다리가 가득차지 않았을 경우 -> 다음 트럭을 다리에 올릴 수 있는지 확인

다음 트럭의 무게 + 현재 다리 위의 트럭 무게 > 최대 무게
다리에 트럭을 올릴 수 없음.
이미 있는 트럭은 한 칸 움직여야 하기에 '0'을 다리에 추가 (시간 +1)
최대 무게보다 낮아서 올릴 수 있다면
sum += 새로운 트럭 (시간 +1)

3. 다리가 가득 찬 경우

가득 찼다는 뜻은 맨 앞의 트럭이 다리의 마지막 부분이라는 뜻이기 때문에 poll로 빼준다.

💡코드

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

        for (int i = 0; i < truck_weights.length; i++) {
            int truck = truck_weights[i];

            while (true) {
                if (bridge.isEmpty()) { // 다리가 비었다면 트럭 추가!
                    bridge.add(truck);
                    sum += truck;
                    time++;
                    break;
                } else if (bridge.size() == bridge_length) { // 다리에 트럭이 전부 찬 경우
                    sum -= bridge.poll(); // 다리를 다 건넜다는 뜻이므로 빼준다
                    
                } else { // 다리에 자리가 남았을 때
                    if (sum + truck <= weight) { // 다음 트럭이 올라갈 수 있는지 무게 체크
                        bridge.add(truck);
                        sum += truck;
                        time++;
                        break;
                    } else { // 못 올라간다면 '0' 을 다리에 올려서 앞에 트럭 한 칸 이동
                        bridge.add(0);
                        time++;
                    }
                }
            }
        }
        int result = time + bridge_length; // 마지막 트럭은 칸 이동을 하기 전에 끝나므로 다리의 길이만큼 더함
        return result;
    }
}