[JAVA] 프로그래머스 | 42583 다리를 지나는 트럭

📝 TIL

- [42583] 다리를 지나는 트럭

 

 

문제를 요약하면 다음과 같다.

 

다리 위에는 bridge_length만큼 트럭이 동시에 올라갈 수 있다.

다리 위 트럭들의 무게 합은 weight보다 작아야 한다.

트럭은 1초마다 한 칸씩 움직인다.

모든 트럭이 다리를 지나려면 몇 초가 걸리는가?

 

 

제한사항

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

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

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

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

 

입출력 예

입출력#1

---

🦔 설계 및 시도

1시간 동안 해결이 안돼서 정답을 본 문제.

 

내가 고민하던건 Queue의 경우 offerLast 즉, 값을 넣으면 빈 공간이 없이 쌓이는데,

이 문제는 wieght가 넘을 경우에 weight가 될 때까지 하나씩 빠지면서 빈 공간의 수는 유지해야 했다.

그래서 이 부분을 어떻게 해결해야 하나 엄청 고민했던 거 같다.

 

 

핵심 포인트는 바로 '0'을 넣는다!

즉 내가 고민한 것처럼, 빈 공간을 체크해줘야하기 때문에

임의 값인 0을 넣어서 해당 자리를 유지해주는 것이었다!

 

 

 

1. 다리를 큐(Queue)로 생각하고, 시간 단위로 한 칸씩 전진시킨다

2. 큐의 길이는 항상 bridge_length(다리처럼 생각하니까!)

3. 트럭이 올라갈 수 있으면 무게를 추가하고, 못 올라가면 0을 넣어 빈 자리 유지

 

흐름을 나타내면 아래와 같다.

시간  다리 상태        무게합
-------------------------------
0    [0, 0, 0]        0
1    [0, 0, 7]        7
2    [0, 7, 0]        7
3    [7, 0, 0]        7
4    [0, 0, 4]        4 (7 빠짐)
5    [0, 4, 5]        9
6    [4, 5, 0]        9
7    [5, 0, 6]        11 → X (6 못 올라감 → 0 넣음)
8    [0, 6, 0]        6 (5 빠짐, 6 올라감)
9    [6, 0, 0]        6
10   [0, 0, 0]        0 (6 빠짐 → 끝)

 

또한 처음에 while(true)를 사용하여, 조건이 맞으면 break하게 했더니

시간 초과가 나서 시간은 계속 흐르고, 그에 따라 트럭의 변화를 구하는 방법으로 다시 풀었다.

 

 

🔥 풀이에 사용된 개념

Deque

- Queue처럼 사용할 때

 

pollFirst() : 맨 앞 트럭 제거offerLast() : 뒤에 트럭 추가

 

---

 

💡 풀이 소스 코드

 

시간복잡도 : O(N)

공간복잡도 : O(N) / N : bridge_length

 

import java.util.*;

class Solution {
    public int solution(int bridge_length, int weight, int[] truck_weights) {
        int answer = 0;
        int sum = 0;
        int i = 0; // 남은 트럭
        int time =0;
        
        Deque<Integer> bridge = new ArrayDeque<>();
        
        // 다리 길이만큼 초기화
        for(int j=0; j<bridge_length; j++) {
            bridge.offerLast(0);
        }
        
        while(i<truck_weights.length){
            time++; // 시간은 계속 1씩 증가
            
            // 제일 앞 트럭 이동
            int out = bridge.pollFirst();
            sum-=out;
            
            // 다음 무게 합이 weight 보다 작을 때
            if(sum+truck_weights[i] <= weight){
                bridge.offerLast(truck_weights[i]);
                sum+=truck_weights[i];
                i++;
            }
            
            // weight보다 클 때 (못올라감)
            else {
                bridge.offerLast(0);
            }
            
        }
        // 지금까지 걸린 시간 + 마지막 트럭 시간(다리 길이)
        return time+bridge_length;
    }
}

 

---

🚀 새로 배운 내용

- 문제 그대로 풀되, 0을 넣어 다리 공간을 유지하는 것이 핵심이었다!

 

 

---

😺  느낀점

- 알고리즘 문제를 풀 때 항상 조건을 나눠서 푸는 습관을 들이자

- 조건을 나눈 후 문제에서 명시된 기준을 체크하는 건 필수

 

*소스 코드는 다음 깃허브에 올라옵니다 - https://github.com/s0ooo0k/Algorithm_Study

GitHub - s0ooo0k/Algorithm_Study: Algorithm Study 문제 및 풀이