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

시간 여유가 있을때마다 알고리즘을 풀려고 노력을 하고 있는데 이 문제 때문에 며칠 흥미를 잃어버렸습니다.

너무 어렵고 안풀려서 고생했어요 ㅠㅠ 큐를 활용한 문제이고 도저히 안풀려서 며칠의 시간 간격을 두면서 풀이를 진행했습니다.

https://programmers.co.kr/learn/courses/30/lessons/42583

프로그래머스

 

문제를 보면서 큐를 활용한 문제풀이를 진행하면 될 것 같다고 생각을 했고 금방 풀 수 있을거라고 생각했지만 어려움이 많은 문제였습니다.

가장 애를 먹었던 부분이 시간이 지나면 트럭을 제거해 줘야하는데 어떻게 제거해줄까라는 부분에서 계속 애를 먹었습니다.

연속으로 트럭이 들어오는 경우까지 생각을 할 경우 제 구현력이 좋지 않아서 인지 계속 해맸습니다.

그래서 다른 분들의 풀이도 참고하면서 문제를 풀었고 가장 핵심은

트럭의 도착 시간 = 현재시간 + 다리의 길이 인 것을 활용해서 문제를 풀 경우 훨씬 쉽게 접근할 수 있습니다.

 

import java.util.*;
class Solution {
    public int solution(int bridge_length, int weight, int[] truck_weights) {
        
        Queue<Integer> bridgeQ = new LinkedList<Integer>();
        int[] arrTime = new int[truck_weights.length];
        int time = 0;
        int idx = 0;
        
        while(true){
            
            // 트럭이 도착할 경우 다리에서 제거해준다.
            if(!bridgeQ.isEmpty() && arrTime[bridgeQ.peek()] == time){
                weight += truck_weights[bridgeQ.poll()];
            }
            
            // 트럭을 추가할 경우
            if(idx < truck_weights.length && truck_weights[idx] <= weight){                
                bridgeQ.add(idx);
                weight -= truck_weights[idx];
                arrTime[idx] = time + bridge_length;
                idx++;    
            }
            
            time++;
            if(bridgeQ.isEmpty())
                break;
        }
        
        return time;
    }
}