[프로그래머스/Level2] 다리를 지나는 트럭 - JAVA

난이도 : Level 2

유형 : 큐 / 구현 / 시뮬레이션

구현 시간 : 40분

링크 : https://school.programmers.co.kr/learn/courses/30/lessons/42583 

프로그래머스

 

 

문제 풀이

시뮬레이션 표를 통해 1초에 한 대씩 움직인다는 것을 유추하고, 1초마다 트럭의 동작이 어떻게 변하는지를 나타내면 되는 문제였다.

아래는 1초 마다 조건을 만족하면 트럭이 나가고, 조건을 만족하면 트럭이 다리 위로 올라오는 코드이다. 현재 문제에서는 괜찮지만, 시간복잡도가 올라간다. 1초를 기준으로 while문이 돌아가기 때문이다.

import java.util.*;

class Solution {
    public int solution(int bridge_length, int weight, int[] truck_weights) {
        int index = 0;
        int totalWeight = 0;
        Queue<int[]> bridge = new ArrayDeque<>(); // {weight, input time}
        int time = 0;
        
        while(index < truck_weights.length || !bridge.isEmpty()) {
            time++;
            
            if(!bridge.isEmpty()){
                int[] truck = bridge.peek();
                if(time >= truck[1] + bridge_length){
                    bridge.poll();
                    totalWeight -= truck[0];
                }
            }
            
            if(bridge.size() < bridge_length && index < truck_weights.length && totalWeight+truck_weights[index] <= weight) {
                bridge.add(new int[]{truck_weights[index], time});
                totalWeight += truck_weights[index];
                index++;
            }
        }
        
        return time;
        
    }
}

 

조금 더 효율적인 풀이는 아래와 같다.

이벤트 드리븐 시뮬레이션으로 바꾼 풀이다.

매 초가 아니라, 이벤트만 처리한다.

1. 트럭이 다리에서 내려오는 시점
2. 트럭이 다리에 올라가는 시점

새 트럭을 올릴 수 없을 때는 시간을 다음 내려오는 시각으로 점프한다.

 

import java.util.*;

class Solution {
    public int solution(int bridge_length, int weight, int[] truck_weights) {
        int n = truck_weights.length;
        int time = 0;               // 현재 시각
        int i = 0;                  // 다음에 올릴 트럭 인덱스
        int onBridgeWeight = 0;     // 다리 위 총 무게

        // 다리 위 상태: {트럭무게, 내려오는 시각}
        ArrayDeque<int[]> bridge = new ArrayDeque<>();

        while (i < n || !bridge.isEmpty()) {
            // Step A: 현재 시각에 내려와야 하는 트럭들 정리
            while (!bridge.isEmpty() && bridge.peekFirst()[1] <= time) {
                onBridgeWeight -= bridge.pollFirst()[0];
            }

            // Step B: 다음 트럭을 올릴 수 있으면 올리고, 다음 초로 이동
            if (i < n 
                && bridge.size() < bridge_length 
                && onBridgeWeight + truck_weights[i] <= weight) {

                bridge.addLast(new int[]{truck_weights[i], time + bridge_length});
                onBridgeWeight += truck_weights[i];
                i++;
                time++;
            } else {
                // Step C: 못 올리면 다음 이벤트(가장 가까운 트럭이 내려오는 시간)로 시간 점프
                if (!bridge.isEmpty()) {
                    time = Math.max(time, bridge.peekFirst()[1]);
                }
            }
        }

        // 보정: 문제 시간 정의(첫 진입을 1초로 세는 관례) 맞추기
        return time + 1;
    }
}