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

문제 링크

1. 문제 해결

트럭이 들어올 때, 나갈 때의 순서가 중요한 문제이다. 다리 무게는 다리에 트럭이 진입할 때, 다 건널 때 발생한다.

1. 현재 ? 시간에 A라는 트럭이 다 건너면, 다리는 A 트럭의 무게 만큼 버틸 수 있는 무게가 복구된다.
2. 다리가 지탱할 수 있는 무게가 복구됬으니 아직 출발하지 않은 트럭의 무게가 다리보다 가벼운 경우, 트럭이 다리에 올라갈 수 있다.

1-1. 전처리

트럭의 정보를 저장할 클래스를 선언한다. 클래스의 변수는 아래와 같다

1. 현재 트럭의 위치
2. 현재 트럭의 무게

1-2. 알고리즘 동작

현재 시간에 트럭이 나가는 것을 먼저 판단하고, 들어오는 것을 생각한다.

1. 다리 위에 있는 트럭이 다리를 다 건넌지 판단한다.
   1-1. 다리 위에 있는 트럭이 다리를 다 건넌 경우, 트럭의 무게 만큼 다리가 버틸 수 있는 무게를 복구시킨다.
2. 현재 다리 무게 >= 기다리고 있는 트럭의 무게일 경우에만 트럭을 다리 위로 올려놓는다.

2. 소스 코드

import java.util.*;
class Solution {
    public int solution(int bridge_length, int weight, int[] truck_weights) {
        int end = 0;
        Queue<Truck> waiting = new LinkedList<>();
        List<Truck> going = new LinkedList<>();
        
        for(int i =0 ; i < truck_weights.length ; i++){
            waiting.add(new Truck(truck_weights[i],1));
        }
        
        int time = 0;
        while(end != truck_weights.length){
            time++;
            int remove =0 ;
            
            for(int i =0 ; i < going.size() ; i++){
                going.get(i).distance++;
                
                if(going.get(i).distance > bridge_length){
                    weight += going.get(i).weight;
                    end++;
                    remove++;
                }
            }
            
            for(int i =0 ; i <remove ; i++)
                going.remove(0); //트럭이 순서대로 들어오기 때문에 선입선출이다.
            
            //다리를 건너는 트럭
            if(!waiting.isEmpty() && waiting.peek().weight <= weight){
                weight -= waiting.peek().weight;
                going.add(waiting.poll());                
            }
        }
        
        return time;
    }
    
    private class Truck{
        int weight, distance;
        
        public Truck(int w , int d){
            this.weight = w;
            this.distance = d;
        }
    }
}