📌 문제
트럭 여러 대가 강을 가로지르는 일차선 다리를 정해진 순으로 건너려 합니다. 모든 트럭이 다리를 건너려면 최소 몇 초가 걸리는지 알아내야 합니다. 다리에는 트럭이 최대 bridge_length대 올라갈 수 있으며, 다리는 weight 이하까지의 무게를 견딜 수 있습니다. 단, 다리에 완전히 오르지 않은 트럭의 무게는 무시합니다.
solution 함수의 매개변수로 다리에 올라갈 수 있는 트럭 수 bridge_length, 다리가 견딜 수 있는 무게 weight, 트럭 별 무게 truck_weights가 주어집니다. 이때 모든 트럭이 다리를 건너려면 최소 몇 초가 걸리는지 구하세요.
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 입출력 풀이
| 경과 시간 | 다리를 지난 트럭 | 다리를 건너는 트럭 | 대기 트럭 |
|---|---|---|---|
| 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초가 걸립니다.
✨ 해결 방법
다리 위를 queue 라고 생각합니다.
트럭을 truck_weights에서 빼내어 queue에 넣어야 하므로 queue와 truck_weights 속 트럭이 하나 이상 있을 때까지, 즉, 한 truck_weights가 모두 비워질 때까지 반복합니다.
queue에 넣을 수 있는 조건은 다음과 같습니다.
1. queue가 빈 배열일 때
2. 앞선 요소들의 합 + 지금 넣을 요소의 합 >= 총 무게 weight
3. 앞선 요소와 지금 넣을 요소의 총 갯수 <= bridge_length
따라서 이 경우에는 truck_weights 조합의 첫 번째 요소를 빼 내어 변수로 선언하고, queue에 무게와 다리를 떠난 시점 (올라탄 시간 + 다리의 길이) 를 합쳐서 넣습니다. 다리에 있는 트럭의 무게의 합인 sum에는 올라탄 트럭의 무게를 더해주고, 첫 번째 요소가 이동했으므로 1초가 지나 minTime을 하나 증가시킵니다.
반대로 queue에 더 포함시킬 수 없는 조건이 있습니다.
queue가 하나 이상 차 있는 경우에,
1. 앞선 요소들의 합 + 넣으려는 요소의 합이 총 무게제한보다 클 때
2. 혹은 앞선 요소 + 현재 요소를 더한 갯수가 올라갈 수 있는 총 갯수 bridge_length보다 클 때
이 경우에는 queue의 첫 번째 요소, 즉 다리에 올라가 있는 첫 요소를 다리에서 내려주고, 해당 요소의 무게와 나간 시간을 저장합니다.
만약 나간 시간보다 현재 저장된 최소 시간이 작다면 결국 나간 시간이 최소 시간이 되므로 새로 대입해주고, 전체 무게의 합에서 나간 트럭의 무게를 빼줍니다.
minTime + 1은 마지막 트럭이 다리를 완전히 지나갔을 때의 시간을 나타냅니다. 주어진 로직에서 minTime은 마지막 트럭이 다리를 빠져나가는 시간이 됩니다. 그러므로 마지막 트럭이 다리를 빠져나가면서 minTime이 갱신되고, minTime + 1을 반환하면 모든 트럭이 다리를 통과하는 데 걸린 총 시간이 됩니다.
💻 solution
function solution(bridge_length, weight, truck_weights) {
let queue = [], minTime = 0, sum = 0;
while (queue.length > 0 || truck_weights.length > 0) {
if (queue.length === 0 || (weight >= sum + truck_weights[0] && queue.length < bridge_length)) {
const truckWeight = truck_weights.shift();
queue.push({ weight: truckWeight, time: minTime + bridge_length });
sum += truckWeight;
minTime++;
} else {
const { weight, time: sec } = queue.shift();
if (minTime < sec) {
minTime = sec;
}
sum -= weight;
}
}
return minTime + 1;
}💻 solution 2
function solution(bridge_length, weight, truck_weights) {
// '다리'를 모방한 큐에 간단한 배열로 정리 : [트럭무게, 얘가 나갈 시간].
let time = 0, qu = [[0, 0]], weightOnBridge = 0;
// 대기 트럭, 다리를 건너는 트럭이 모두 0일 때 까지 다음 루프 반복
while (qu.length > 0 || truck_weights.length > 0) {
// 1. 현재 시간이, 큐 맨 앞의 차의 '나갈 시간'과 같다면 내보내주고,
// 다리 위 트럭 무게 합에서 빼준다.
if (qu[0][1] === time) weightOnBridge -= qu.shift()[0];
if (weightOnBridge + truck_weights[0] <= weight) {
// 2. 다리 위 트럭 무게 합 + 대기중인 트럭의 첫 무게가 감당 무게 이하면
// 다리 위 트럭 무게 업데이트, 큐 뒤에 [트럭무게, 이 트럭이 나갈 시간] 추가.
weightOnBridge += truck_weights[0];
qu.push([truck_weights.shift(), time + bridge_length]);
} else {
// 3. 다음 트럭이 못올라오는 상황이면 얼른 큐의
// 첫번째 트럭이 빠지도록 그 시간으로 점프한다.
// 참고: if 밖에서 1 더하기 때문에 -1 해줌
if (qu[0]) time = qu[0][1] - 1;
}
// 시간 업데이트 해준다.
time++;
}
return time;
}좋은 코드 같지만 아직 해석이 덜 되었습니다
