알고리즘/프로그래머스

다리를 지나는 트럭 (후)

베리영young 2024. 2. 26. 15:15

사용 알고리즘: 큐

사용 언어: java

 

import java.io.*;
import java.util.*;

/**
"순서대로"

처음에서 들어갈 땐 +1, 마지막에서 나갈 땐 시간 증가 없음
*/
// https://minhamina.tistory.com/241

// 0을 집어 넣기
// 다리를 queue로 만드는 거 까지는 생각했는데...
class Solution {
    //queue의 길이 == bridge_length
    //queue 안에 있는 값의 합이 weight 초과하면 안 됨
    //truck_weights 순서대로 움직임(변수 idx를 두고 관리)
    //더 올라올 수 없으면 queue.add(0) 하기
    //뭐든 올라올 때마다 time++;
    //    내려갈 때는 time 변화 x
    public int solution(int bridge_length, int weight, int[] truck_weights) {
        Queue<Integer> bridge = new ArrayDeque<>();
        int time = 0;
        int idx = 0; // truck_weights.length 미만이어야 함
        int sum = 0; //순간마다 다리에 올라간 무게 합 구하려면 시간 오래 걸리니까 여기에 저장
        
        while(idx < truck_weights.length) {
            if(bridge.isEmpty()) {
                sum += truck_weights[idx];
                bridge.add(truck_weights[idx++]);
                time++;
            }
            if(idx >= truck_weights.length) break;
            
            if(bridge.size() >= bridge_length) {
                sum -= bridge.poll();
            }
            
            //올라갈 수 있는데
            //무거워서 못 올라갈 때
            if(sum + truck_weights[idx] > weight) {
                bridge.add(0);
                time++;
            }
            //가벼워서 더 올라갈 수 있을 때
            else {
                sum += truck_weights[idx];
                bridge.add(truck_weights[idx++]);
                time++;
            }
        }
        
        //마지막 애는 올라만 갔으니까 '다리 길이'만큼 더해주기
        return time + bridge_length;
    }
}

 

인사이트

다리에 큐를 써야 하는 건 인지함,

트럭이 더 올라가지 않고 시간만 가야하는 경우 어떻게 처리할지 생각 못 함 => 큐에 0을 넣으면 된다.

=> 0 활용