[프로그래머스 - Lv2] 다리를 지나는 트럭 - java

프로그래머스 : 다리를 지나는 트럭 ( Lv-2 )

---

트럭 여러 대가 강을 가로지르는 일차선 다리를 정해진 순으로 건너려 합니다. 모든 트럭이 다리를 건너려면 최소 몇 초가 걸리는지 알아내야 합니다. 다리에는 트럭이 최대 bridge_length대 올라갈 수 있으며, 다리는 weight 이하까지의 무게를 견딜 수 있습니다. 단, 다리에 완전히 오르지 않은 트럭의 무게는 무시합니다. 예를 들어, 트럭 2대가 올라갈 수 있고 무게를 10kg까지 견디는 다리가 있습니다. 무게가 [7, 4, 5, 6]kg인 트럭이 순서대로 최단 시간 안에 다리를 건너려면 다음과 같이 건너야 합니다.

 

따라서, 모든 트럭이 다리를 지나려면 최소 8초가 걸립니다. solution 함수의 매개변수로 다리에 올라갈 수 있는 트럭 수 bridge_length, 다리가 견딜 수 있는 무게 weight, 트럭 별 무게 truck_weights가 주어집니다. 이때 모든 트럭이 다리를 건너려면 최소 몇 초가 걸리는지 return 하도록 solution 함수를 완성하세요.

 

 

제한 조건

---

bridge_length는 1 이상 10,000 이하입니다. weight는 1 이상 10,000 이하입니다. truck_weights의 길이는 1 이상 10,000 이하입니다. 모든 트럭의 무게는 1 이상 weight 이하입니다.

 

 

입출력 예

---

 

 

 

풀이

---

Queue를 잘 사용하여야하는 문제입니다.

문제에서 Truck을 주어진 배열에 맞추어 순서대로 뽑아내라하였으니, array에 순차적으로 바로 접근하여 풀어내는방법과, Queue에 집어넣어 푸는방법이 있겠습니다.

 

제 경우에는 문제 접근을 이렇게 하였습니다.

1. bridge의 size보다 트럭의 갯수가 작고, weight가 bridge에 올라간 트럭들의 weight 합 + 트럭Queue의 맨 앞 트럭의 weight보다 같거나 크면 bridge 진입

2. 여기서 진입한 트럭은 Node의 형태로 담겨, weight와, truck이 도착하는 시간(tick)을 저장

3. while문의 tick마다 bridge queue의 맨 앞 트럭노드의 arrive time(pass_time)을 확인, tick이 pass_time보다 같거나 크면 해당 트럭 도착표시

 

이를 계속 반복합니다.

 

여기서, 성능을 줄일 수 있는 팁은, 각각의 tick이 돌 때마다 bridge queue의 트럭 weight 합을 계속 구하지 말고, 한번 구해놓은 후 트럭이 들어올 때, 나갈 때 구해놓은 합에서 더하거나, 빼가는 슬라이딩 윈도우의 형식으로 접근하면 됩니다.

 

정답은 코드는 아래와 같습니다.

import java.util.*;

class Node {
    private int truck_weight;
    private int pass_time;

    public Node(int truck_weight, int pass_time) {
        this.truck_weight = truck_weight;
        this.pass_time = pass_time;
    }

    public int getTruck_weight() {
        return truck_weight;
    }

    public int getPass_time() {
        return pass_time;
    }
}

class Solution {
    public int solution(int bridge_length, int weight, int[] truck_weights) {

        Queue<Integer> truckOrder = new LinkedList<>();

        Queue<Node> bridge = new LinkedList<>();

        for(int truck : truck_weights) {
            ;            truckOrder.offer(truck);
        }

        int nowTime = 0;
        int nowWeight = 0;

        Node node;

        while(!truckOrder.isEmpty() || !bridge.isEmpty()){
            nowTime++;

            if(!bridge.isEmpty() && bridge.peek().getPass_time() <= nowTime){
                Node outNode = bridge.poll();
                nowWeight -= outNode.getTruck_weight();
            }

            if(!truckOrder.isEmpty() && truckOrder.peek() + nowWeight <= weight && bridge.size() < bridge_length) {
                int truck = truckOrder.poll();
                node = new Node(truck, nowTime + bridge_length);
                bridge.offer(node);
                nowWeight += node.getTruck_weight();
            }

        }

        int answer = nowTime;
        return answer;
    }
}