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

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

🙋‍♂️ 들어가며

이 문제를 보니 O(N)으로 q를 통해 {time, w} 형태로 풀면 되겠다는 생각이 들었다

테스트 케이스를 직접 작성하여 다음과 같은 흐름이 그려졌다

시간, 무게
1 - 7
2 - 7
3 - 4
4 - 4, 5
5 - 5
6 - 6
7 - 6
8 - []

시간을 1초부터 시작하면, 3초일때 다리에 있는 트럭무게인 7kg를 제거하고 새로운 4kg를 올려야하는 것을 발견했다

그래서 다리에서 트럭을 내린 이후, 다리에 트럭을 올릴 수 있는지 순서로 로직을 짜야한다는 것을 확신했다.

최종적으로 작성한 구조는 다음과 같다

1. q 생성

2-1. 내릴 수 있는지?

2-2. q가 비었고 더이상 다리에 올릴 트럭이 없다면 종료

2-3. 인덱스 초과일때

3. 시간 추가

✅ O(N)

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

class Solution {
    public int solution(int bridge_length, int weight, int[] truck_weights) {
        
        // 1. q 생성 (시간, 무게)
        Queue<int[]> q = new LinkedList<>();
        
        // 2. 계산
        int time = 1;
        int N = truck_weights.length;
        int idx = 0;
        int limit = 0;
        while (true) {
            // 2-1. 내릴 수 있는지?
            if (!q.isEmpty()) {
                int[] cur_pos = q.peek();
                int first_t = cur_pos[0];
                int diff = time - first_t;
                // 2-1-a. 만약 diff == 다라길이 라면
                if (diff == bridge_length) {
                    // 2-1-b. 적발
                    int[] caught_pos = q.poll();
                    int caught_w = caught_pos[1];
                    limit -= caught_w;
                }
            }
            
            // 2-2. q가 비었고 더이상 다리에 올릴 트럭이 없다면 종료
            if (q.isEmpty() && idx >= N) break;
            
            // 2-3. 인덱스 초과라면
            if (idx >= N) {
                time++;
                continue;
            }
            
            // 2-4. 트럭이 다리에 올라올 수 있다면?
            int cur_w = truck_weights[idx];
            if (weight >= limit + cur_w) {
                limit += cur_w;
                q.add(new int[] {time, cur_w});
                idx++;
            }
            
            // 3. 시간 추가
            time++;
            
        }
        
        return time;
    }
}