[Java 알고리즘] 프로그래머스 문제풀이, 다리를 지나는 트럭 (Queue)

다리를 지나는 트럭

문제 설명

트럭 여러 대가 강을 가로지르는 일 차선 다리를 정해진 순으로 건너려 합니다. 모든 트럭이 다리를 건너려면 최소 몇 초가 걸리는지 알아내야 합니다. 트럭은 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 함수를 완성하세요.

제한 조건

1. bridge_length는 1 이상 10,000 이하입니다. 2. weight는 1 이상 10,000 이하입니다. 3. truck_weights의 길이는 1 이상 10,000 이하입니다. 4. 모든 트럭의 무게는 1 이상 weight 이하입니다.

 

입출력 예

bridge_length	weight	truck_weights	return
2	10	[7, 4, 5, 6]	8
100	100	[10]	101
100	100	[10, 10, 10, 10, 10, 10, 10, 10, 10, 10]	110

 

나의 풀이

import java.util.*;

class Solution {
    public int solution(int bridge_length, int weight, int[] truck_weights) {
        // bridge queue -> sum lower than weight / size < bridge_length
        Queue<Truck> bridge = new LinkedList<Truck>();
        Queue<Truck> truckQueue = getTruckQueue(truck_weights); // trucks

        // after bridge
        List<Truck> result = new ArrayList<Truck>();

        int time = 0;

        // exit if result.size() == truck_weights.length
        while(result.size() != truck_weights.length) {
            checkBridgeOverTruck(bridge, result, time);
            if(truckQueue.size() > 0 && 
               sumBridgeWeight(bridge) + truckQueue.peek().weight <= weight) {
                
                // condition true => task
                Truck bridgingTruck = truckQueue.poll();
                bridgingTruck.start = time;
                bridgingTruck.end = time + bridge_length;
                bridge.add(bridgingTruck);

            }
            time++;
        }

        return time;
    }

    private void checkBridgeOverTruck(Queue<Truck> bridge, List<Truck> result, int time) {
        Truck peek = bridge.peek();
        if(peek == null) return;
        if (peek.end == time) { // out bridge
            result.add(bridge.poll());
            return;
        }
    }

    public Queue<Truck> getTruckQueue(int[] truck_weights) {
        Queue<Truck> truckQueue = new LinkedList<Truck>();
        for(int i =0; i<truck_weights.length; i++) {
            Truck truck = new Truck();
            truck.weight = truck_weights[i];
            truckQueue.add(truck);
        }
        return truckQueue;
    }

    public int sumBridgeWeight(Queue<Truck> bridge) {
        int sum = 0;
        for(Truck weight : bridge) {
            sum += weight.weight;
        }
        return sum;
    }

    class Truck {
        public int weight;
        public int start = -1;
        public int end = -1;

		//for print
        @Override
        public String toString() {
            return String.format("Truck [weight=%s, start=%s, end=%s]", weight, start, end);
        }
    }
}

Truck 클래스

 - weight는 해당 트럭의 무게

 - start 는 해당 트럭이 다리를 올라간 시간

 - end 는 해당 트럭이 다리를 내려올 시간

 Queue의 타입클래스를 정의하였습니다. start와 end는 다리에 올라선 순간 결정됩니다.

 

checkBridgeOverTruck 메소드

 - bridge 큐에 있는 선입 Truck 클래스의 end 값을 현재의 time 과 비교하여 내릴시간인지 아닌지 체크하여 bridge 큐에서 poll 처리합니다.

 

sumBridgeWeight 메소드

 - 다리에 있는 트럭의 weight 값을 더합니다. Truck을 Bridge 큐에 넣을지 말지를 결정하는 플래그의 조건으로 사용됩니다.

 

bridge enqueue / dequeue 작업 중 무엇을 먼저할 지 고민을 많이했지만 순서가 사실 다리에서 내리고 새로 타는 트럭의 무게초과 여부를 결정해야합니다. 따라서 처음 checkBridgeOverTruck 메소드에서는 bridge의 값이 empty 할 것이므로 아무 작업도 하지않고 지나가고 첫번째 Truck 객체를 태우게 될 것입니다.