190102 스택&큐 (3) 다리를 지나는 트럭

2019-01-02

스택&큐 (3) 다리를 지나는 트럭

문제 설명

트럭 여러 대가 강을 가로지르는 일 차선 다리를 정해진 순으로 건너려 합니다. 모든 트럭이 다리를 건너려면 최소 몇 초가 걸리는지 알아내야 합니다. 트럭은 1초에 1만큼 움직이며, 다리 길이는 bridge_length이고 다리는 무게 weight까지 견딥니다. ※ 트럭이 다리에 완전히 오르지 않은 경우, 이 트럭의 무게는 고려하지 않습니다.

예를 들어, 길이가 2대까지, 무게 10kg까지 견디는 다리가 있습니다. 무게가 [7, 4, 5, 6]kg인 트럭이 순서대로 최단 시간 안에 다리를 건너려면 다음과 같이 건너야 합니다.

경과 시간 다리를 지난 트럭 다리를 건너는 트럭 대기 트럭
0 [] [] [7,4,5,6]
1~2 [] [7] [4,5,6]
3 [7] [4] [5,6]
4 [7] [4,5] [6]
5 [7,4] [5] [6]
6~7 [7,4,5] [6] []
8 [7,4,5,6] [] []

따라서, 모든 트럭이 다리를 지나려면 최소 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 이하입니다.
풀이 과정

  • 대기중인 트럭/ 다리 위 트럭 두 개의 큐를 이용한다.

  • 대기중인 트럭의 무게와 다리위 트럭 무게의 합이 다리가 견딜 수 있는 무게를 넘지 않으면 다리위 트럭 큐에 대기중인 트럭을 넣는다.

  • 계속 반복하다가 대기중인 트럭과 다리 위 트럭 모두 이동이 완료되면 결과값 리턴

import java.util.*;

class Truck{
    int loc;
    int weight;
    public Truck(int w){
        this.loc=0;
        this.weight=w;
    }
}

class Solution {
    public int solution(int bridge_length, int weight, int[] truck_weights) {
        int answer=0;
        int total_weight=0;
        int time=0;
        
        Queue<Truck> t1=new LinkedList<>(); // 대기 트럭
        for(int tw:truck_weights){
            t1.offer(new Truck(tw));
        }
        
        Queue<Truck> t2=new LinkedList<>();// 다리 위 트럭
        total_weight+=t1.peek().weight;
        t2.offer(t1.poll());
        
        while(!t2.isEmpty()){
            time++;
            
            for(Truck t:t2){
                t.loc++;
            }
            
            if(t2.peek().loc>bridge_length){
                total_weight-=t2.poll().weight;
            }
            
                if(t1.isEmpty()==false&&total_weight+t1.peek().weight<=weight){
                    total_weight+=t1.peek().weight;
                    t1.peek().loc++;
                    t2.offer(t1.poll());
                }
            }
        answer=time;
        return answer;
    }
}

http://sunpil.tistory.com/44 <- 이분의 주석힌트를 보고 풀었다.

나는 큐 문제에 굉장히 약함을 알 수 있었다… 좀더 천천히 꼼꼼하게 푸는 버릇을 들여야 할 것 같다.