프로그래머스 | 다리를 지나는 트럭

📍문제 설명📍

트럭 여러 대가 강을 가로지르는 일차선 다리를 정해진 순으로 건너려 합니다. 모든 트럭이 다리를 건너려면 최소 몇 초가 걸리는지 알아내야 합니다. 다리에는 트럭이 최대 bridge_length대 올라갈 수 있으며, 다리는 weight 이하까지의 무게를 견딜 수 있습니다. 단, 다리에 완전히 오르지 않은 트럭의 무게는 무시합니다.

예를 들어, 트럭 2대가 올라갈 수 있고 무게를 10kg까지 견디는 다리가 있습니다. 무게가 [7, 4, 5, 6]kg인 트럭이 순서대로 최단 시간 안에 다리를 건너려면 다음과 같이 건너야 합니다.


따라서, 모든 트럭이 다리를 지나려면 최소 8초가 걸립니다.

solution 함수의 매개변수로 다리에 올라갈 수 있는 트럭 수 bridge_length, 다리가 견딜 수 있는 무게 weight, 트럭 별 무게 truck_weights가 주어집니다. 이때 모든 트럭이 다리를 건너려면 최소 몇 초가 걸리는지 return 하도록 solution 함수를 완성하세요.

---

📚입출력 예시📚

---

❌실패한 풀이❌

function solution(bridge_length, weight, truck_weights) {
    let answer = 0;
    let bridge = [];
    let bridgeWeight = 0;
    
    while(truck_weights.length > 0) {
        answer++;
        
        if(bridge.length === bridge_length) {
            bridgeWeight -= bridge.shift();
        }
        
        if(bridgeWeight + truck_weights[0] <= weight) {
            let truck = truck_weights.shift();
            bridge.push(truck);
            bridgeWeight += truck;
        }
    }
    
    answer += bridge_length;
    return answer;
}

---

💯성공한 풀이💯

function solution(bridge_length, weight, truck_weights) {
    let answer = 0;
    let bridge = [];
    let bridgeWeight = 0;
    
    while(truck_weights.length > 0) {
        answer++;
        
        if(bridge.length === bridge_length) {
            bridgeWeight -= bridge.shift();
        }
        
        if(bridgeWeight + truck_weights[0] > weight) {
            bridge.push(0);
            continue;
        }
        
        let truck = truck_weights.shift();
        bridge.push(truck);
        bridgeWeight += truck;
    }
    
    answer += bridge_length;
    return answer;
}

💡문제 접근 방식💡

스택 큐 문제여서 그렇게 어려운 문제는 아니였다.
처음 틀렸던 풀이는 bridgeWeight 와 truck_weights[0] 의 값을 합친값이 weight 보다 작을때
그때 truck_weights 배열에서 하나씩 꺼내고 bridge 배열에 넣는다.

처음 방식대로 풀었더니 첫번째 테스트에서 시간초과가 났다.
왜 그런지 살펴보니
bridgeWeight 와 truck_weights[0] 의 값을 합친값이 weight 보다 큰 경우가 발생하기 때문이다.

문제의 예시처럼 [7,4,5,6] 중에 7까지는 실행되지만, 7 + 4 가 실행 될 때 weight인 10을 넘어버리기때문에 while이 무한루프에 빠졌던 것이다.

그래서 문제가 되던 조건문을 수정하였다.