출처 : https://programmers.co.kr/learn/courses/30/lessons/42583
문제
트럭 여러 대가 강을 가로지르는 일차선 다리를 정해진 순으로 건너려 합니다. 모든 트럭이 다리를 건너려면 최소 몇 초가 걸리는지 알아내야 합니다. 다리에는 트럭이 최대 bridge_length대 올라갈 수 있으며, 다리는 weight 이하까지의 무게를 견딜 수 있습니다. 단, 다리에 완전히 오르지 않은 트럭의 무게는 무시합니다.
예를 들어, 트럭 2대가 올라갈 수 있고 무게를 10kg까지 견디는 다리가 있습니다. 무게가 [7, 4, 5, 6]kg인 트럭이 순서대로 최단 시간 안에 다리를 건너려면 다음과 같이 건너야 합니다.
경과 시간 다리를 지난 트럭 다리를 건너는 트럭 대기 트럭
0 [] [] [7,4,5,6]
1~2 [] [7] [4,5,6]
3 [7] [4] [5,6]
4 [7] [4,5] [6]
5 [7,4] [5] [6]
6~7 [7,4,5] [6] []
8 [7,4,5,6] [] []따라서, 모든 트럭이 다리를 지나려면 최소 8초가 걸립니다.
solution 함수의 매개변수로 다리에 올라갈 수 있는 트럭 수 bridge_length, 다리가 견딜 수 있는 무게 weight, 트럭 별 무게 truck_weights가 주어집니다. 이때 모든 트럭이 다리를 건너려면 최소 몇 초가 걸리는지 return 하도록 solution 함수를 완성하세요.
제한 조건
bridge_length는 1 이상 10,000 이하입니다.
weight는 1 이상 10,000 이하입니다.
truck_weights의 길이는 1 이상 10,000 이하입니다.
모든 트럭의 무게는 1 이상 weight 이하입니다.
입출력 예
bridge_length weight truck_weights return
2 10 [7,4,5,6] 8
100 100 [10] 101
100 100 [10,10,10,10,10,10,10,10,10,10] 110접근 방법
먼저 다리에 올라간 트럭이 먼저 나와야 하므로 큐를 사용했다.
큐의 한 노드에는 다리에 올라간 시각과 해당 트럭의 인덱스를 저장한다.
가장 먼저 올라간 트럭이 다리를 모두 건널 시간만큼 다리 위에 있었다면
큐에서 제거하고, 현재 다리 위에 있는 트럭의 무게에서
해당 트럭의 무게만큼 제외한다.
다리를 벗어난 트럭의 인덱스가 마지막 인덱스라면 벗어나는 시간(1초)를 더해주고 return한다.
현재 다리 위에 있는 트럭의 무게에 다음 트럭의 무게를 더했을 때 버틸 수 있는 무게라면 큐에 새 트럭이 올라간 시간과 인덱스를 추가하고 시간을 1 증가한다.
아니라면 다음 트럭이 다리를 지날 시간만큼 시간을 증가한다.
코드
class Queue {
constructor() {
this.queue = [];
}
offer(item) {
this.queue.push(item);
}
poll() {
return this.queue.shift();
}
peek() {
return this.queue[0];
}
}
function solution(bridge_length, weight, truck_weights) {
let time = 0,
idx = 0,
sum = 0,
num = truck_weights.length;
const queue = new Queue();
queue.offer([time++, idx]);
sum += truck_weights[idx++];
while (true) {
if (time - queue.peek()[0] == bridge_length) {
let out = queue.poll();
sum -= truck_weights[out[1]];
if (out[1] === num - 1) {
time++;
break;
}
}
if (sum + truck_weights[idx] <= weight) {
queue.offer([time++, idx]);
sum += truck_weights[idx++];
} else time += time - queue.peek()[0];
}
return time;
}