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

문제

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

풀이

1. Queue로 사용할 데이터들의 전처리를 진행한다.
   • 출발하는 트럭 배열을 Trucks Queue로 재선언한다.
   • Bridge의 길이만큼 무게 0으로 채워둔 Bridge Queue를 선언한다.
2. 알고리즘 시작.
   1. Bridge Queue의 맨 앞 무게를 빼낸다.
      • 빼낸 무게가 0보다 클 경우, 현재 Bridgee Queue의
        총 무게에서 차감 후 도착지 Queue에 삽입한다.
   2. 현재 Bridge Queue의 총 무게와 대기중인 Trucks Queue의
      첫 번째 트럭 무게 합이 허용 무게를 넘는지 비교한다.
      • 넘지 않는다면, Trucks Queue에서 Bridge Queue로 이동시키고,
        Bridge Queue의 총 무게를 업데이트한다.
      • 넘는다면, 그냥 0을 채워넣어서 트럭의 움직임을 기록한다.

import java.util.*;
class Solution {
    public int solution(int bridge_length, int weight, int[] truck_weights) {
        Queue Bridge = new LinkedList();
        Queue Trucks = new LinkedList();
        Queue Arrived = new LinkedList();
        // Bridge Queue에 0 채워넣기.
        for(int i = 0; i < bridge_length; i++) Bridge.add(0);
        // truck_weights 배열을 Trucks Queue로 변환.
        for(int i = 0; i < truck_weights.length; i++) Trucks.add(truck_weights[i]);
        // 시간측정 변수, Bridge Queue 총 무게 변수.
        int timer = 0, bridgeWeight = 0;
        // 도착한 트럭의 수가 시작 트럭 수와 같아질 때 까지 루프.
        while(Arrived.size() < truck_weights.length){
            timer += 1; // 시간측정.
            // Bridge Queue의 가장 앞 값 추출
            int arrive = (int)Bridge.poll();
            if(arrive > 0){ // 차량이었다면 도착지에 추가, 다리 무게 업데이트.
                Arrived.add(arrive);
                bridgeWeight -= arrive;
            }
            // 남은 트럭이 있고, 현재 다리의 무게와 추가될 트럭의 무게 합이 허용량 내라면,
            if(!Trucks.isEmpty() && bridgeWeight + (int)Trucks.peek() <= weight){
                bridgeWeight += (int)Trucks.peek(); // 다리 무게 업데이트.
                Bridge.add(Trucks.poll());          // Trucks Queue -> Bridge Queue 이동.
            } else Bridge.add(0);    // 아니면 그냥 0 추가해서 트럭 이동 표현.

        }
        return timer;
    }
}

확실히 풀어본 문제라고 20분만에 쉽게 풀어냈다.
전처리부터 확실하게 잘 설계하면, 핵심 알고리즘 구상도 쉽게 된다.