[프로그래머스 알고리즘 고득점 Kit][스택/큐][Java] 다리를 지나는 트럭

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

프로그래머스

 

문제 핵심

• 트럭은 1초에 1칸씩 이동 (지문엔 명시 안 되어 있고, 예시 표로 유추해야 함)
• 트럭 1대가 다리를 완전히 통과하는 데 정확히 bridge_length초 소요
• 다리 위 트럭들의 무게 합이 weight를 넘으면 안 됨 (대기 중인 트럭 무게는 무시)

풀이 전략

• 큐 2개로 관리: waitingQ(아직 다리에 안 오른 트럭), bridgeQ(현재 다리 위 트럭, {진입시각, 무게} 저장)
• time을 1씩 증가시키며 매초 두 단계를 순서대로 체크
  1. 내리기: bridgeQ 맨 앞 트럭의 진입시각 + bridge_length == time이면 다리에서 빼고 무게 차감
  2. 태우기: waitingQ 맨 앞 트럭을 태워도 totalWeight + 무게 <= weight면 태우고 무게 누적
• waitingQ와 bridgeQ가 둘 다 빌 때까지 반복, 최종 time이 정답

import java.util.*;

class Solution {
    public int solution(int bridge_length, int weight, int[] truck_weights) {
        Queue<Integer> waitingQ = new ArrayDeque<>();
        Queue<int[]> bridgeQ = new ArrayDeque<>();
        
        for(int t : truck_weights) {
            waitingQ.add(t);
        }
        
        int time = 0;
        int totalWeight = 0;
        while(!waitingQ.isEmpty() || !bridgeQ.isEmpty()) {
            time++;
            
            if(!bridgeQ.isEmpty()) {
                int[] bridgeTruck = bridgeQ.peek();
                
                if(bridgeTruck[0] + bridge_length == time) {
                    bridgeQ.poll();
                    totalWeight -= bridgeTruck[1];
                    
                }
            }
            
            if(!waitingQ.isEmpty()) {
                int waitingTruck = waitingQ.peek();
                
                if(totalWeight + waitingTruck <= weight && bridgeQ.size() < bridge_length) {
                    waitingQ.poll();
                    bridgeQ.add(new int[] {time, waitingTruck});
                    totalWeight += waitingTruck;
                }
            }
        }
        
        return time;
    }
}