[JAVA] 프로그래머스 스택/큐 -【다리를 지나는 트럭】

---

import java.util.*;
class Solution {
    public int solution(int bridge_length, int weight, int[] truck_weights) {

        Queue<Integer> bridge = new LinkedList<>();
        Queue<Integer> truck = new LinkedList<>();
        
        for(int i=0;i<truck_weights.length;i++){
            truck.offer(truck_weights[i]);
        }
        
        for(int i=0;i<bridge_length;i++){
            bridge.offer(0);
        }
        
        // 첫번째 차 출발
        int totalWeight = 0;
        int totalTruckNum = 0;
        int time = 0;
        
        while(true){
           
            if(truck.isEmpty()){
                break;
            }
            //트럭이 내릴 차례인 경우
            if(bridge.peek()!=0){
                totalWeight-=bridge.poll();
                totalTruckNum--;
            }else{
                bridge.poll();
            }
      
            int waitingTruck = truck.peek();
            //차가 더 올라올 수 있는 경우 (다리에 공간이 있으면서 무게가 초과되지 않을 때)
            if((bridge_length>=totalTruckNum)&&(weight>=totalWeight+waitingTruck)){
                bridge.offer(truck.poll());
                totalWeight+=waitingTruck;
                totalTruckNum++;
            //차가 더 못올라오는 경우
            }else{
                bridge.offer(0);
            }        
            time++;          
        }
        
        time+=bridge_length;
        
        return time;
    }
}

 

겨우겨우 혼자 힘으로 풀었다.

---

먼저 코드 흐름은 예제 첫번째 상황이라면, 

 

bridge 큐를 선언해서, 다리 길이만큼 '0' 을 넣어놨다.

 

그리고 truck 큐를 선언해서, 트럭 무게를 넣어놨다.

 

bridge = [ 0 , 0 ]

truck = [ 7 4 5 6 ]

 

---

그리고 truck이 다리를 지날 수 있는 조건은 두가지가 있는데,

 

다리에 트럭이 올라갈 공간이 있는가 + 트럭의 총 무게 합이 제한 무게를 넘지 않는가이다.

 

따라서, 조건을 만족하면 truck 큐에서 poll()을 한뒤 bridge큐에 offer()한다.

만약 조건을 만족하지 못하면, 그냥 '0'을 offer()한다.

 

즉, 단계별로 bridge큐를 보면

 

    0초          1초           2초          3초           4초          5초           6초          7초             8초

[ 0 , 0 ] → [ 0 , 7 ] → [ 7 , 0 ] → [ 0 , 4 ] → [ 4 , 5 ] → [ 5 , 0 ] → [ 0 , 6 ] → [ 6 , 0 ] → [ 6 , 0 ] 

  

위와 같이 나오도록 코드를 구현하는게 목표이다.

 

---

먼저, while 루프문은 truck 큐가 완전히 비면 탈출하도록 구현하였다.

 

따라서, 위 bridge 큐 예시 그림에서 마지막 트럭 무게는 6이므로

 

    6초

 [ 0 , 6 ] 

 

에서 while문을 탈출할 것이다. 어차피 마지막 트럭이고 다리 전체 길이만큼 더 가면 끝난다.

 

whlie문을 탈출하기 전까지 계산한 time에 bridge length를 더해주면 된다. (6초 + 2초)

 

---

bridge.peek()을 해서, 0이면 별다른 로직이 필요없지만 0이 아닌 경우는 트럭이 내렸다는 의미이므로

 

트럭 갯수와, 현재 다리에 있는 트럭 무게를 감소시켜주면 된다.

 

참고로, 먼저 트럭을 내리는 작업을 해야, 다리 위 트럭 무게를 계산할때 편하다.