✉ Question
문제 설명
트럭 여러 대가 강을 가로지르는 일차선 다리를 정해진 순으로 건너려 합니다. 모든 트럭이 다리를 건너려면 최소 몇 초가 걸리는지 알아내야 합니다. 다리에는 트럭이 최대 bridge_length대 올라갈 수 있으며, 다리는 weight 이하까지의 무게를 견딜 수 있습니다. 단, 다리에 완전히 오르지 않은 트럭의 무게는 무시합니다.
예를 들어, 트럭 2대가 올라갈 수 있고 무게를 10kg까지 견디는 다리가 있습니다. 무게가 [7, 4, 5, 6]kg인 트럭이 순서대로 최단 시간 안에 다리를 건너려면 다음과 같이 건너야 합니다.
따라서, 모든 트럭이 다리를 지나려면 최소 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 이하입니다.
💌 Answer
스택/큐 문제
- 다리를 건너는 트럭들이
delay없이 붙어서 다리를 건널 경우의 시간이 최소시간이므로 최종 시간은min+delay(최소시간 + 지연시간)이다. trucks: 스택 구조
➡ 가장 마지막 인덱스의 트럭을 다리에 올릴 수 있을 때pop해서 꺼낸다.bridge: 큐 구조
➡ 다리의 제한무게를 넘지 않을 경우 트럭을push해서 추가해주고,total무게를 증가시킨다. 제한무게 때문에 트럭을 더 이상 올릴 수 없을 경우 트럭 무게 대신 0을push해주고 0이 추가되는 만큼 지연되므로delay시간을 증가시킨다.
➡idx는 맨 앞의 트럭의 위치를 나타낸다.idx가 0이면 다리의 맨 앞의 트럭이 다리를 완전히 건널 차례이므로total무게에서bridge.shift()로 꺼낸 무게를 감소시켜준다. 이제 맨 앞의 트럭은idx + 1인덱스에 있으므로idx를 증가시켜준다.
function solution(bridge_length, weight, truck_weights) {
let answer = 0;
let min = bridge_length + truck_weights.length;
let delay = 0;
let bridge = [];
let trucks = [];
let total = 0;
let idx = bridge_length;
for(let i = truck_weights.length - 1; i >= 0; i--) {
trucks.push(truck_weights[i]);
}
while(trucks.length > 0) {
let target = trucks[trucks.length - 1];
if(idx === 0) {
total -= bridge[0];
bridge.shift();
idx++;
}
if(total + target <= weight) {
total += target;
bridge.push(target);
trucks.pop();
}else {
delay++;
bridge.push(0);
}
idx--;
}
answer = min + delay;
return answer;
}
자바스크립트에는 스택이나 큐를 구현한 라이브러리가 없어서 Array의 pop과 push를 사용해 배열을 스택으로 사용했다.
큐는 push로 enpueue를, shift로 dequeue를 하는 식으로 자료구조를 이용했으나, shift는 아무래도 배열의 앞 요소를 제거하고 뒤의 요소들을 앞으로 당겨주는 과정이 있으므로 효율성이 좋을 것 같진 않다.
효율성까지 고려하는 문제였다면 stack과 queue를 연결리스트 등으로 직접 구현해서 사용해야 하지 않을까...😅
.
.
.
여러모로 시행착오가 많았던 문제였다!💦
