다리를 지나는 트럭 - 스택/큐

INPUT

1. 특정 무게 weight 만큼의 무게를 감당할 수 있는 길이 bridge_length 의 다리
2. 배열에 들어있는 순서대로 이동할 트럭의 무게를 담은 배열 truck_weights

조건

1. 다리 위에 있는 트럭들의 무게의 합은 weigth 이하여야 한다.
2. truck_weights 의 앞 인덱스 부터 트럭이 건너야 한다.
3. 다리 위에서 1초가 흐를 때 마다 한 칸씩 트럭이 움직인다.

OUTPUT

truck_weigths 배열에 들어있는 트럭들이 모두 다리를 건너는 데 걸리는 최단 시간

LOGIC

기다리고 있는 트럭들의 무게를 담고 있는 waiting 큐, 다리의 정보를 나타내는 bridge 큐 를 만들었다.

우선 다리가 비어있음을 나타내기 위해 bridge 큐에 (다리의 길이 - 1) 만큼 "0" 을 채워준다. 가장 초기에 진입할 트럭인 truck_weigths[0] 을 큐에 넣어주고, waiting 큐 에선 한개 빼준다. 이로써 초기 세팅은 끝난다 (1초 경과)

waiting 에 들어있는 트럭들이 없어지면 끝나게 while 문을 생성했다. waiting 이 원소가 0개가 되는 경우 바로 종료되므로, 마지막엔 bridge 큐의 크기만큼 시간을 추가해준다. (마지막 원소의 진입 부터 나갈 때 까지 걸리는 시간)

1초가 지날 때 마다 앞에서 한칸 뺀다. 새로운 트럭이 진입할 수 있는 경우인지 확인한다. (무게)

1. 가능 할 경우 bridge 큐에 새 트럭을 넣어준다.

2. 불가능 할 경우 "0" 을 넣어준다. 다리의 해당 칸에 자리가 비어있음을 표현.

모든 과정에서 bridge 큐의 무게의 합에 대한 정보를 가지고 있는 sum 을 수시로 업데이트 해준다.

import java.util.*;
class Solution {
    public int solution(int bridge_length, int weight, int[] truck_weights) {
        int answer = 1;
        
        // 초기 세팅
        Queue<Integer> waiting = new LinkedList<>();
        for(int data : truck_weights){
            waiting.add(data);
        }
        Queue<Integer> bridge = new LinkedList<>();
        for(int i=0;i<bridge_length-1;i++){
            bridge.add(0);
        }
        bridge.add(waiting.poll());
        int sum = truck_weights[0];
        
        // 로직 시작
        while (waiting.size()!=0) {
        	
            // 다리에 있는 트럭의 무게 합 업데이트
            sum-=bridge.poll();
			
            // 새 트럭을 넣을 수 있는 경우
            if (sum + waiting.peek() <= weight) {
            
            	// 새 트럭을 waiting 큐에서 뺌
                int truck = waiting.poll();
                
                // 새 트럭을 bridge 큐에 추가
                bridge.add(truck);
                
                // 다리에 있는 트럭의 무게 합 업데이트
                sum+=truck;
            } 
            
            // 새 트럭을 넣을 수 없는 경우
            else {
            	// 빈칸 삽입
                bridge.add(0);
            }
            
			// 1초 지남
            answer++;
        }
        
        // waiting 이 비자마자 루프가 종료되므로, 마지막 진입한 트럭이 나가는 시간 추가
        return answer+bridge.size();
    }
}

회고

1. bridge 큐의 무게를 구하는 과정에서, 매 작업 마다 무게들의 합을 새로 구하였더니 시간초과는 나지 않았지만 매우 비효율적이였다. 그래서 sum 을 이용해서 새로 구할 필요 없이 무게를 더하고 빼는 수준으로만 작업하였다.

2. 다리의 정보를 나타내는 큐는 bridge_length 을 크기로 가지는 큐로 만들고 싶었는데, Apache Commons Collections 4 라는 외부 라이브러리를 사용하면 CircularFifoQueue를 만들 수 있다고 하였다. 아마 큐의 단점을 보안하기 위한 circular queue 인 것 같다. 이번엔 그냥 코드 상에서 큐의 길이를 바꾸어 주었다.