문제 설명
트럭 여러 대가 강을 가로지르는 일 차선 다리를 정해진 순으로 건너려 합니다. 모든 트럭이 다리를 건너려면 최소 몇 초가 걸리는지 알아내야 합니다. 트럭은 1초에 1만큼 움직이며, 다리 길이는 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 이하입니다.
function solution(bridge_length, weight, truck_weights) {
let onQueue = [];
let finishQueue = [];
let i = 1; // 경과시간
const len = truck_weights.length;
while(i){
if(onQueue.length !== 0){
if(onQueue[0][1] + bridge_length === i){
finishQueue.push(onQueue[0][0]);
weight += onQueue[0][0];
onQueue.shift();
}
} // ∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙ 1st if문
if(weight - truck_weights[0] >= 0){
onQueue.push([truck_weights[0] , i]); //출발시간
weight -= truck_weights[0];
truck_weights.shift();
} // ∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙ 2nd if문
if(finishQueue.length === len){
break;
}
i++;
}
return i;
}1) 트럭 배열의 첫 번째 차량이 출발하면 현재 지나가는 트럭의 배열인 onQueue가 비어 있으므로 2nd if문부터 시작된다. 지나가는 트럭을 onQueue에 넣을 때는 출발시점 i를 꼭 같이 넣어준다.
2) 제한 무게 weight에서 onQueue로 push되는 트럭의 무게를 빼서 여유 무게를 설정한다. onQueue에서 트럭을 뺐기 때문에 다음 연산의 편의를 위해서 트럭 배열의 첫 번째 요소를 shift한다.
3) 이 문제는 전형적인 큐에 대한 상황이므로 onQueue의 길이가 0 이 아닐 때, onQueue의 첫 번째 요소의 출발시간과 bridge_length의 합이 현재의 시간 i와 같아지면 그것을 지나간 트럭 배열 finishQueue에 넣고, 그 넣은 트럭의 무게만큼 제한무게를 다시 회복한다.
4) 위 과정을 반복하여 finishQueue.length = 원래 트럭배열 길이가 같아지면 멈추고 i 리턴.
처음에 접근이 어려웠던 이유
✔︎ 표만 봐서는 한 눈에 안들어왔다. 보기 편한 시간 눈금으로 다시 그렸다.
✔︎ bridge_length(다리의 길이)는 곧 트럭 한 대의 주파시간과 연관이 깊다. 주어진 힌트를 최대한 활용
✔︎ weight(제한무게)는 가변적이다. 두 개의 큐를 거칠 때마다 갱신한다.
✔︎ 1st if문을 2nd밑으로 쓰면 선발 트럭과 후발 트럭의 바통터치가 안된다.
