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

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

프로그래머스

---

import java.util.*;
class Solution {
    public int solution(int bridge_length, int weight, int[] truck_weights) {
        int time = 0;
        Queue<Truck> queue = new LinkedList<>();
        int idx = 0, nw = 0;
        Set<Integer> leaveTime = new HashSet<>();
        while (idx < truck_weights.length) {
            if (leaveTime.contains(time) && !queue.isEmpty()) {
                nw -= queue.poll().weight;
                leaveTime.remove(time);
            }else if ((queue.size() == bridge_length || nw + truck_weights[idx] > weight)&& !queue.isEmpty()) {
                time = queue.peek().enteredTime + bridge_length;
            }else{
                nw += truck_weights[idx];
                queue.add(new Truck(idx, truck_weights[idx], time));
                leaveTime.add(time + bridge_length);
                time++;idx++;
            }
        }
        return time + bridge_length;
    }

    private class Truck {
        int idx;
        int weight;
        int enteredTime;

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

도로에 있는 트럭들을 큐에 넣고, 조건이 맞으면 빼거나 넣는 방식으로 구현함

 

# k번째 트럭이 도로에 올라가야 하는 상황인 경우

1. 도로(큐)에 여유가 되는 경우

    => 트럭을 도로에 올리고 (queue.add(truck_k)), now_weight 갱신, time+bridge_length로 k번째 트럭 나가는 시간 저장

    => time+1, k+1로 다음 차례로 넘어감

2. k번째 트럭이 올라가지 못하는 경우

    2-1. 도로에 트럭이 가득 찬 경우 (queue.size == length) 

    2-2. k번째 트럭을 올리면 허용 무게를 초과하는 경우(nowWeight + truck_weight[k] > weight)

    => 도로 제일 앞에있는 트럭이 나올 때 까지 기다린 후, 다시 무게 체크 위해 1번 부터 시작

• 나가는 시간 체크를 위해 Set을 사용했다. 나가는 시간은 고유하므로 idx를 붙여 Map으로 만드는 대신 그냥 넣어줌
• 트럭이 모두 다리를 건너는데 필요한 시간은 트럭이 모두 다리에 올라온 시간 + 다리 길이 이므로 끝까지 계산할 필요 없음

---

복잡해질까봐 대기큐는 생략했는데, 외려 사용하는게 좀 더 직관적이고 훨씬 흐름이 깔끔해보이는 듯... 가독성 좀 신경쓰면서 짜자....

import java.util.*;
class Solution {
    public int solution(int bridge_length, int weight, int[] truck_weights) {
        Queue<Truck> waitQueue = new LinkedList<>();
        Queue<Truck> bridgeQueue = new LinkedList<>();
        for(int t : truck_weights){
            waitQueue.offer(new Truck(t));
        }
        int time = 0, curWeight = 0;
        while (!waitQueue.isEmpty() || !bridgeQueue.isEmpty()) {
            time++;
            if (bridgeQueue.isEmpty()) {//다리 큐가 비었을 경우
                Truck t = waitQueue.poll();
                curWeight += t.weight; // 기존 무게 + 유입 트럭 무게
                bridgeQueue.offer(t);
                continue;
            }
            for (Truck t : bridgeQueue) {
                t.getMove(); //다리 위 트럭들 위치 한칸씩 이동
            }
            //맨 앞 트럭 도착했으면 무게 갱신
            if (bridgeQueue.peek().move > bridge_length) {
                Truck t = bridgeQueue.poll();
                curWeight -= t.weight;
            }
            //기다리는 트럭 있고, 다리 위에 올릴 여유 있으면 트럭 추가
            if(!waitQueue.isEmpty() && curWeight + waitQueue.peek().weight <= weight){
                Truck t = waitQueue.poll();
                curWeight += t.weight;
                bridgeQueue.offer(t);
            }
        }

        return time;
    }

    private class Truck {
        int weight;
        int move;

        public Truck(int weight) {
            this.weight = weight;
            this.move = 1;
        }
        public void getMove(){
            move++;
        }
    }
}

출처 : https://school.programmers.co.kr/learn/courses/30/lessons/42583/solution_groups?language=java