[프로그래머스] 다리를 지나는 트럭(Java, Lv2, 큐)

programmers.co.kr/learn/courses/30/lessons/42583?language=java

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

 

 

## 접근방법

---

모든 트럭이 다리를 지나는 시간을 구하면 된다. 트럭마다 무게가 다르고, 다리가 견딜 수 있는 하중 무게도 생각해야 한다.

 

 

 

큐를 이용하면, 트럭들의 무게와 다리를 지나는 시간을 저장할 수 있다 .큐를 사용하는 이유는, 큐의 후입선출 방식때문이다. 즉, 나중에 들어온 트럭들은 순차적으로 큐에 쌓이고, 큐의 포인터가 가리키는 것은 첫번째 원소이다. 

 

 

 

다음 트럭이 들어오기 위해서는, 가장 먼저 들어온 트럭 순으로 다리를 지나는 시간이 되는 순간, 큐에서 제거되면 된다.시간 복잡도는 다리의 길이 * 트럭의 개수가 될 것이다.

 

 

 

좀 더 좋은 풀이를 생각해보고 싶었지만, 현재 상황으로는 큐가 가장 적합한거 같다. 어떤 트럭이 들어가기 위해서는, 트럭들이 다리를 지나는 완료 시간들을 순차적으로 저장하는 자료구조가 필요했기 때문이다.

 

 

## 해설코드

---

import java.util.*;
 
class Solution {
    class Item{
        int w, t;
        Item(int w, int t){
            this.w = w;
            this.t = t;
        }
    }
 
    public int solution(int bridge_length, int weight, int[] truck_weights) {
        int answer = 0;
        int curWeight = 0;
        int time = 0;
        int tIdx = 0;
 
        Queue<Item> q = new LinkedList<>();
        while(tIdx != truck_weights.length){
            if(!q.isEmpty() && q.peek().t == time){
                curWeight -= q.peek().w;
                q.poll();
            }
            
            if(truck_weights[tIdx] + curWeight <= weight){
                q.add(new Item(truck_weights[tIdx], time + bridge_length));
                curWeight += truck_weights[tIdx];
                tIdx++;
            }
 
            time++;
        }
 
        return time + bridge_length;
    }
}