문제
트럭 여러 대가 강을 가로지르는 일차선 다리를 정해진 순으로 건너려 합니다. 모든 트럭이 다리를 건너려면 최소 몇 초가 걸리는지 알아내야 합니다. 다리에는 트럭이 최대 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점)
function solution(bridge_length, weight, truck_weights) {
let time = 0;
let current_weight = 0;
let bridge = new Array(bridge_length).fill(0);
while (truck_weights.length > 0) {
// 한 번 순회할 때마다 매 초를 가리킴
time++;
// 1초가 지나면 맨 앞 차가 다리를 빠져나가고, 무게도 그만큼 감소
current_weight -= bridge.shift();
// 다음 차가 들어올 때 최대 무게를 넘기는지 체크. 안 넘으면 다음 차 push
if (current_weight + truck_weights[0] <= weight) {
let truck = truck_weights.shift();
bridge.push(truck);
// 현재 무게에 새로 들어온 차 더해 줌.
current_weight += truck;
// 다음 차가 들어올 때 최대 무게를 넘기면 다음 차 대신 0 push
} else {
bridge.push(0);
}
}
// 더 이상 다음 차가 없으므로 bridge_length초 만큼 지나면 모든 차가 다리를 빠져나감.
time += bridge_length;
return time;
}문제에서 주어진 첫 예시를 가지고 매 초마다 어떤 일이 일어나는지 살펴보자.
bridge_length weight truck_weights return
2 10 [7,4,5,6] 8time === 0
bridge = [0, 0]
current_weight = 0
time === 1
bridge = [0, 7]
current_weight = 7
0번째 원소인 0이 빠져나갈 때, 그 다음 원소인 7이 들어와도 최대 무게인 10을 넘기지 않으므로 맨 뒤 원소로 7이 들어온다. (if문 진입)
time === 2
bridge = [7, 0]
current_weight = 7
0번째 원소인 0이 빠져나갈 때, 그 다음 원소인 4가 들어오면 최대 무게인 1을 넘기므로, 맨 뒤 원소로 0이 들어온다. (else문 진입)
time === 3
bridge = [0, 4]
current_weight = 4
0번째 원소인 7이 빠져나갈 때, 그 다음 원소인 4가 들어와도 최대 무게인 10을 넘기지 않으므로 맨 뒤 원소로 4가 들어온다. (if문 진입)
time === 4
bridge = [4, 5]
current_weight = 9
0번째 원소인 0이 빠져나갈 때, 그 다음 원소인 5가 들어와도 최대 무게인 10을 넘기지 않으므로 맨 뒤 원소로 5가 들어온다. (if문 진입)
time === 5
bridge = [5, 0]
current_weight = 5
0번째 원소인 4가 빠져나갈 때, 그 다음 원소인 6이 들어오면 최대 무게인 1을 넘기므로, 맨 뒤 원소로 0이 들어온다. (else문 진입)
time === 6
bridge = [0, 6]
current_weight = 6
0번째 원소인 5가 빠져나갈 때, 그 다음 원소인 6이 들어와도 최대 무게인 10을 넘기지 않으므로 맨 뒤 원소로 5가 들어온다. (if문 진입)
time === 7
bridge = [6]
current_weight = 6
7초가 되면 이미 truck_weights의 길이가 0이므로(대기 중인 트럭이 더 이상 없음) while문을 빠져나온다.
사실상 7초와 8초는 마지막 트럭이 진입할 때부터 도착할 때까지의 시간을 나타내므로, time 6에 2를 더해준 8이 답이 되고, 이런 논리는 코드의 마지막 부분에 나타나 있다. 하지만 가상 세계 속의 트럭을 표현하기 위해 여기에 매 초 다리에 무슨 일이 일어나는지 기록은 해보겠다.
time === 8
bridge = []
current_weight = 0
8초가 되었을 때 마지막 트럭이 도착하고 bridge도 빈 배열이 된다.
