알고리즘 / Java / 프로그래머스 - 다리를 지나는 트럭

프로그래머스 - 다리를 지나는 트럭

코딩테스트 연습 - 다리를 지나는 트럭

문제 해설

기다리고 있는 트럭들의 큐와 다리를 지나고 있는 트럭들의 큐, 이렇게 2개의 큐를 만들어 놓으면 쉽게 해결할 수 있습니다.

그리고 각자의 상태관리를 위해 Bridge 객체와 Truck 객체를 만들어 주었습니다.

 

정답 코드

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

class Solution {
    class Bridge {
        //다리가 감당할 수 있는 무게
        private int weight;
        private int length;
        //현재 올라가 있는 트럭들의 무게
        private int currentWeight;

        public Bridge(int weight, int length, int currentWeight) {
            this.weight = weight;
            this.length = length;
            this.currentWeight = currentWeight;
        }
    }

    class Truck {
        //트럭이 다리를 지나기 시작한 시간
        private int startTime;
        private int weight;

        public Truck(int startTime, int weight) {
            this.startTime = startTime;
            this.weight = weight;
        }

        public void setStartTime(int startTime) {
            this.startTime = startTime;
        }
    }

    public int solution(int bridge_length, int weight, int[] truck_weights) {
        //시작 시간 초기화
        int time = 1;
        Bridge bridge = new Bridge(weight, bridge_length, 0);

        //대기 트럭 큐에 모든 트럭들을 넣습니다.
        Queue<Truck> wait = new LinkedList<>();
        for (int truck_weight : truck_weights) {
            wait.offer(new Truck(1, truck_weight));
        }
        
        //다리를 지나는 트럭 큐에 하나의 트럭을 올려 놓습니다.
        Queue<Truck> onBridge = new LinkedList<>();
        crossBridge(bridge, onBridge, wait, time);

        while (!onBridge.isEmpty()) {
            //완료한 트럭이 있는지 확인
            Truck onBridgeTruck = onBridge.peek();
            if (onBridgeTruck.startTime <= time - bridge.length) {
                Truck completeTruck = onBridge.poll();
                bridge.currentWeight -= completeTruck.weight;
            }
            
            //트럭을 다리에 추가할 수 있다면 새로운 트럭 출발
            if (!wait.isEmpty()) {
                Truck waitTruck = wait.peek();
                if (bridge.currentWeight + waitTruck.weight <= bridge.weight) {
                    crossBridge(bridge, onBridge, wait, time);
                }
            }
            
            //모두 완료되었다면 리턴
            if (onBridge.isEmpty() && wait.isEmpty()) {
                return time;
            }
            time++;
        }
        return time;
    }

    private void crossBridge(Bridge bridge, Queue<Truck> onBridge, Queue<Truck> wait, int time) {
        Truck truck = wait.poll();
        truck.setStartTime(time);
        onBridge.offer(truck);
        bridge.currentWeight += truck.weight;
    }
}