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

🤔 문제

🔗

트럭 여러 대가 강을 가로지르는 일차선 다리를 정해진 순으로 건너려 합니다. 모든 트럭이 다리를 건너려면 최소 몇 초가 걸리는지 알아내야 합니다. 다리에는 트럭이 최대 bridge_length대 올라갈 수 있으며, 다리는 weight 이하까지의 무게를 견딜 수 있습니다. 단, 다리에 완전히 오르지 않은 트럭의 무게는 무시합니다.

solution 함수의 매개변수로 다리에 올라갈 수 있는 트럭 수 bridge_length, 다리가 견딜 수 있는 무게 weight, 트럭 별 무게 truck_weights가 주어집니다. 이때 모든 트럭이 다리를 건너려면 최소 몇 초가 걸리는지 return 하도록 solution 함수를 완성하세요.

👊 풀이과정

두개의 연결리스트를 이용해야 하는 문제다.

아직 출발하지 않은 트럭들이 담긴 trucks와 현재 다리 위에 있는 트럭들이 담인 bridge를 만든다.

💻 소스코드

java.util.*;

class Solution {
	public static int solution(int bridge_length, int weight, int[] truck_weights) {
		int answer=0;
		int current =0;    //    현재 다리 위에 있는 트럭들의 무게 총합

        LinkedList<Truck> trucks = new LinkedList<>();    //    대기중인 트럭들
        LinkedList<Truck> bridge = new LinkedList<>();    //    다리위에 있는 트럭들

        for (int t : truck_weights) {
            trucks.offer(new Truck(t,bridge_length));
        }

        while(!trucks.isEmpty() || !bridge.isEmpty()) {
            answer++;
            //    다리 위에 트럭이 있을 경우 앞으로 이동
            if(!bridge.isEmpty()) {
            	for(Truck t : bridge) {
            		t.move--;
				}
                if(bridge.getFirst().move == 0) {
                    current -= bridge.poll().weight;
                }
			}               
			//    다리에 새 트럭을 올릴 수 있는 경우 출발하기
			if(!trucks.isEmpty() && trucks.peek().weight + current <= weight && bridge.size() <= bridge_length) {
				bridge.offer(trucks.poll());
				current += bridge.peekLast().weight;
			}
        }
        return answer;
    }  
}


class Truck {
    int weight;    //    트럭 무게
    int move;    //    다리를 건너기 위해 움직여야 하는 횟수(다리 길이)

    Truck(int weight, int move) {
        this.weight=weight;
        this.move=move;
    }
}