[프로그래머스][스택&큐][JS] 다리를 지나는 트럭

Teasan·2022년 7월 5일

Algorythm

목록 보기

12/17

다리를 지나는 트럭

문제 설명

문트럭 여러 대가 강을 가로지르는 일차선 다리를 정해진 순으로 건너려 합니다. 모든 트럭이 다리를 건너려면 최소 몇 초가 걸리는지 알아내야 합니다. 다리에는 트럭이 최대 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 이하입니다.

입출력 예

수도 코드

// 시간
0 [_,_,_,_] [_,_] [7,4,5,6]
1 [_,_,_,_] [_,7] [4,5,6] // 1. 트럭이 다리에 올라감
2 [_,_,_,_] [7,_] [4,5,6] // 2. 한계하중이 걸리면 못 올라감 3. 다리에서 전진
3 [7,_,_,_] [_,4] [5,6]. // 4. 다리 끝에 도착하면 내려간다
4 [7,_,_,_] [4,5] [6].
5 [7,4,_,_] [5,_] [6] // 못 올라감
6 [7,4,5,_] [_,6] []
7 [7,4,5,_] [6,_] []
8 [7,4,5,6] [_,_] []

풀이 코드

function solution(bridge_length, weight, truck_weights) {
    let bridge = Array.from({length: bridge_length}, () => 0);
    let answer = 0;

    while(bridge.length) { // truthy 할 때까지
        bridge.shift();
        answer += 1;

        if(truck_weights.length) { // truthy 하다면

            let total = bridge.reduce((prev, curr) => prev + curr, 0);
            if(total + truck_weights[0] <= weight) {
                bridge.push(truck_weights.shift());
            } else {
                bridge.push(0)
            }
        }
    }

테스트

테스트 1 〉 통과 (32.07ms, 31.9MB)
테스트 2 〉 통과 (2091.73ms, 32.7MB)
테스트 3 〉 통과 (0.15ms, 30.1MB)
테스트 4 〉 통과 (274.33ms, 32.2MB)
테스트 5 〉 통과 (2594.27ms, 34MB)
테스트 6 〉 통과 (753.75ms, 33.1MB)
테스트 7 〉 통과 (16.80ms, 31.8MB)
테스트 8 〉 통과 (0.78ms, 30.2MB)
테스트 9 〉 통과 (10.48ms, 32.1MB)
테스트 10 〉 통과 (0.81ms, 30.2MB)
테스트 11 〉 통과 (0.25ms, 30.2MB)
테스트 12 〉 통과 (0.45ms, 30MB)
테스트 13 〉 통과 (7.66ms, 31.7MB)
테스트 14 〉 통과 (0.12ms, 30MB)