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

프로그래머스 고득점 kit 스택/큐 문제인 다리를 지나는 트럭 문제다.

백준에서 풀어봤던 적이 있던 문제라 어렵지 않게 풀 수 있었다.

다만 처음 접하는 경우 까다로운 조건이 몇 개 있어서 좀 어려울 수도 있다.

 

 

✅ 핵심 풀이

먼저 다리의 길이만큼 큐에 0을 넣었다.

트럭 한 개가 다리 길이 1만큼을 차지 하므로 트럭이 올라가지 않은 다리는 0으로 두는 것이다.

q.poll() == 0 인 경우 지나간 트럭은 없고 q.poll() q.add() 해줄 때 마다 큐에 존재하는

트럭이 왼쪽으로 이동하므로 이 방법을 사용 하면 전체 다리 길이와 트럭이 다리를 건너는 시점을

따로 신경쓰지 않아도 된다.

 

그리고 truck_weights의 마지막 인덱스 값이 큐에 넣어진 경우

해당 트럭이 나갈때까지 q.poll() q.add(0) 할 필요 없이 while 반복문을 break 해주고

지금까지의 시간을 담은 answer 과 다리 길이(마지막 트럭이 건너는데 필요한 시간) 를

더한 값을 return 해주면 된다.

중간에 큐에 들어있는 다른 트럭들을 신경 쓸 필요가 없고

마지막 트럭이 나가는데 필요한 시간 = 다리 길이가 되기 때문이다.

 

🚨 CODE

import java.util.*;

class Solution {
    public int solution(int bridge_length, int weight, int[] truck_weights) {
        int answer = 0;
		Queue<Integer> q = new LinkedList<>();
        
        // 큐 초기화
        for(int i = 0; i<bridge_length; i++) {
        	q.add(0);
        }
        
        int curW = 0; // 다리의 현재 무게
        int idx = 0; // 다리를 건널 차례
        while(true) {
        	curW -= q.poll();
        	// 현재 무게가 제한 무게를 초과하지 않고 idx가 트럭 배열 길이 보다 작으면
        	if(curW + truck_weights[idx] <= weight && idx < truck_weights.length) {
        		q.add(truck_weights[idx]); // 트럭 지나가기 시작
        		if(idx == truck_weights.length - 1) { // 마지막 트럭인지 확인
        			answer++;
        			break;
        		}
        		curW += truck_weights[idx]; // 현재 무게 갱신
        		idx++;
        	}else
        		q.add(0); // 무게 제한에 걸려 다음 트럭이 못 올라오면 add 0
        	answer++;
        }
		return answer + bridge_length;
    }
}