문제 설명
트럭 여러 대가 강을 가로지르는 일차선 다리를 정해진 순서대로 건너야 합니다. 모든 트럭이 다리를 건너려면 최소 몇 초가 걸리는지 알아내야 합니다. 다리에는 트럭이 최대 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초가 걸립니다.
제한 조건
bridge_length: 1 이상 10,000 이하weight: 1 이상 10,000 이하truck_weights의 길이: 1 이상 10,000 이하- 모든 트럭의 무게는 1 이상
weight이하
입출력 예
-
입력:
2,10,[7, 4, 5, 6] -
출력:
8 -
입력:
100,100,[10] -
출력:
101 -
입력:
100,100,[10, 10, 10, 10, 10, 10, 10, 10, 10, 10] -
출력:
110
문제 해결 방법
- 각 트럭이 다리에 오르고 다리를 건너는 과정을 시뮬레이션합니다.
- 현재 다리 위에 있는 트럭의 무게와 위치를 추적합니다.
- 새로운 트럭이 다리에 오를 수 있는지 확인하고, 올릴 수 있다면 올립니다.
- 트럭이 다리를 완전히 건너면 다리에서 내립니다.
해결 전략
다리 위의 트럭들을 큐로 관리하여, 각 트럭이 다리 위에 있는 시간과 다리의 현재 하중을 추적합니다. 이를 통해 매 초마다 다리 위의 상태를 업데이트합니다.
코드 구현
function solution(bridge_length, weight, truck_weights) {
let time = 0;
let bridge = [];
let bridge_weight = 0;
while (truck_weights.length > 0 || bridge.length > 0) {
// 시간 경과
time++;
// 다리를 건넌 트럭을 제거
if (bridge.length > 0 && bridge[0].end_time === time) {
bridge_weight -= bridge[0].weight;
bridge.shift();
}
// 새로운 트럭을 다리에 올리기
if (truck_weights.length > 0 && bridge_weight + truck_weights[0] <= weight) {
let truck_weight = truck_weights.shift();
bridge.push({ weight: truck_weight, end_time: time + bridge_length });
bridge_weight += truck_weight;
}
}
return time;
}코드 설명
-
변수 초기화:
time: 경과 시간을 추적합니다.bridge: 다리 위의 트럭들을 관리합니다. 각 트럭은{ weight, end_time }형태로 저장됩니다.bridge_weight: 현재 다리 위의 총 무게를 추적합니다.
let time = 0; let bridge = []; let bridge_weight = 0; -
큐 처리:
- 트럭들이 다리를 모두 건널 때까지 반복합니다.
- 매 초마다 시간을 증가시킵니다.
- 다리를 건넌 트럭을 큐에서 제거하고, 다리 무게에서 해당 트럭의 무게를 뺍니다.
- 새로운 트럭이 다리에 오를 수 있는지 확인하고, 올릴 수 있다면 트럭을 다리에 올리고, 다리 무게에 해당 트럭의 무게를 추가합니다.
while (truck_weights.length > 0 || bridge.length > 0) { time++; if (bridge.length > 0 && bridge[0].end_time === time) { bridge_weight -= bridge[0].weight; bridge.shift(); } if (truck_weights.length > 0 && bridge_weight + truck_weights[0] <= weight) { let truck_weight = truck_weights.shift(); bridge.push({ weight: truck_weight, end_time: time + bridge_length }); bridge_weight += truck_weight; } } -
결과 반환:
- 모든 트럭이 다리를 건너면 경과 시간을 반환합니다.
return time;
예시 테스트
console.log(solution(2, 10, [7, 4, 5, 6])); // 8
console.log(solution(100, 100, [10])); // 101
console.log(solution(100, 100, [10, 10, 10, 10, 10, 10, 10, 10, 10, 10])); // 110이 코드는 주어진 예시 입력에 대해 올바른 결과를 출력합니다. 다리 위의 트럭 상태를 시뮬레이션하여 모든 트럭이 다리를 건너는 데 걸리는 시간을 정확히 계산합니다.
결론
이번 포스팅에서는 트럭이 다리를 건너는 시뮬레이션 문제를 해결하는 방법을 살펴보았습니다. 큐 자료구조를 사용하여 다리 위의 트럭 상태를 관리하고, 모든 트럭이 다리를 건너는 데 걸리는 시간을 계산하는 과정을 이해할 수 있습니다. 코딩 테스트를 준비하는 여러분께 도움이 되길 바랍니다. 다음 포스팅에서는 또 다른 문제로 찾아뵙겠습니다. 감사합니다!
