[스택/큐] 다리를 지나는 트럭 - Java코드 ★★★

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

코딩테스트 연습 - 다리를 지나는 트럭

 

문제

 

이해

다리에 트럭이 선입 선출되는 문제이므로 FILO이 아닌 FIFO에 큐를 이용한다.

큐에 들어간 무게합은 wegith보다 작은지 검사하면서 다리라는 Queue를 활용하여

무게의 합을 관리하면서 초를 재야한다.

 

설계

문제 체감상 Lv2가 아닌 Lv3정도는 되는것 같다.

다리의 길이만큼을 가지는 Queue를 설계하고 싶었지만, 

큐는 사이즈를 정할 수 없었다. 

 

하지만, 미리 다리의 길이만큼 0의 원소들을 넣어두고

무게합을 체크하면서 offer와 poll을 해주면, 좀 더 쉽게 초를 구할 수 있다.  

 

풀이

import java.util.LinkedList;
import java.util.Queue;
class Solution {
    public static int solution(int bridge_length, int weight, int[] truck_weights) {
        Queue<Integer> q = new LinkedList<Integer>();
        for (int i=0;i<bridge_length ; i++) q.add(0); // 큐를 다리길이만큼 0원소로 초기화
        int sec=0,sum=0;
        for (int t : truck_weights) {
            while(sum+t - q.peek() >weight){
                sum-=q.poll();
                q.offer(0);
                sec++;
            }
            sum = sum-q.poll()+t;
            q.offer(t);
            sec++;
        }
        return sec+bridge_length;
    }
}

 

생각을 꽤나 해야하는 문제이다.

큐를 초기화시켜놓고 돌리더라도,

체크로직부분과 리턴부분까지 디테일하게 신경 써주어야 한다.