큐를 이용해서 푸는 문제입니다.
큐로 표현하는 사물은 '다리'(a)와 '순서대로 기다리고 있는 트럭들'(b)이 있습니다.
매 루프마다 다리(a)위의 트럭들의 시간들과 정답인 '시간'(ans)을 증가시킵니다.
시간이 지나서
a의 맨 앞의 요소 c의 시간이 다리의 길이보다 크다면
a에서 c를 제거하고 sum_of_weight에서 c의 무게 만큼 감소시킵니다.
위 과정을 반복하다가 a와 b에 더 이상 트럭이 남아있지 않다면 루프를 탈출합니다.
function solution(bridge_length, weight, truck_weights) {
const bridge = [];
let ans = 0;
let weight_of_trucks_on_bridge = 0;
// 4. 1, 2, 3을 반복하다가 a와 b에 더 이상 트럭이 남아있지 않다면 루프를 탈출합니다.
while (truck_weights.length || bridge.length) {
// 2. 매 루프마다 다리(a)위의 트럭들의 시간들과 정답인 '시간'(ans)을 증가시킵니다.
bridge.forEach(truck => truck[1]++);
ans++;
/**
* 3.
* 시간이 지나서
* a의 맨 앞의 요소 c의 시간이 다리의 길이보다 크다면
* a에서 c를 제거하고 sum_of_weight에서 c의 무게 만큼 감소시킵니다.
*/
if (bridge.length && bridge[0][1] > bridge_length) {
let truck = bridge.shift();
weight_of_trucks_on_bridge -= truck[0];
}
/**
* 1.
* b의 맨 앞에 있는 트럭의 무게와 '다리 위의 총 트럭들의 무게'(sum_of_weight)의 합이
* 다리가 버틸 수 있는 무게보다 작거나 같다면
* b의 맨 앞의 트럭을 빼와서 **'[트럭 무게, 시간]'(c)**으로 가공해서 **a**에 넣고
* sum_of_weight**를 **c**의 무게만큼 증가시킵니다.
*/
const truck_weight = truck_weights[0];
if (weight_of_trucks_on_bridge + truck_weight <= weight) {
weight_of_trucks_on_bridge += truck_weight;
bridge.push([truck_weight, 1]);
truck_weights.shift();
}
}
return ans;
}
다리에 트럭이 몇 대 있는지는 체크 안해도 됩니다.
어차피 다리에 트럭이 넘치기도 전에
트럭을 빼내야 최소 시간을 구할 수 있기 때문입니다.