[프로그래머스/Java] 다리를 지나는 트럭(스택/큐) 풀이

프로그래머스 알고리즘 고득점 Kit 스택&큐 파트 중 '다리를 지나는 트럭' 문제를 Java로 풀어보았다.

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

프로그래머스

 

 on_bridge라는 이름의 queue를 만들어서 트럭이 다리 위에 올라가는 상황에서 queue에 트럭의 weight를 add 해줬다. add 해줄 때 cur_weight에 무게를 더해주고, poll 할 때 빼주어서, 현재 다리 위에 올라가 있는 트럭들의 무게의 합을 확인한다. 만약 add 해줄 요소가 없다면 0을 add 해줘서, 다리가 꽉 차면 맨 앞 트럭을 poll 해줄 수 있도록 한다.

 트럭들을 모두 다리 위에 올리고 나서는 현재 다리 위 트럭들이 얼마의 시간이 더 지나야 모두 다리를 완전히 건널 수 있는지를 구해서 answer에 더해준다.

import java.util.*;

class Solution {
    public int solution(int bridge_length, int weight, int[] truck_weights) {
        Queue<Integer> on_bridge = new LinkedList<Integer>();
        
        on_bridge.add(truck_weights[0]);
        int cur_weight = truck_weights[0];
        int answer = 1;
        int i = 1;
        while (i < truck_weights.length) {
            answer++;
            if (on_bridge.size() == bridge_length) {
                cur_weight -= on_bridge.poll();
            }
            if (cur_weight + truck_weights[i] <= weight) {
                on_bridge.add(truck_weights[i]);
                cur_weight += truck_weights[i++];
            } else on_bridge.add(0);
        }
        answer += (bridge_length - on_bridge.size());
        while (!on_bridge.isEmpty()) {
            on_bridge.poll();
            answer++;
        }
        
        return answer;
    }
}