[Algorithm] 프로그래머스 - 다리를 지나는 트럭 (스택, 큐 - Stack, queue )

프로그래머스 문제입니다.

문제 설명

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

 

---

입출력 

---

입출력 설명

예제 #1

문제 설명의 예시와 같습니다.

---

문제풀이

function solution(bridge_length, weight, truck_weights) {
    // (1)
    let time = 0, weight_current = 0, count_pop = 0
    let bridge = new Array(bridge_length).fill(0)
    const count_truck = truck_weights.length
    // (2)
    while (count_pop < count_truck) {
        let pop = 0
        // (3)
        if (weight_current + truck_weights[0]  - bridge[0] <= weight) pop = truck_weights.shift()
        // (4)
        weight_current += pop
        bridge.push(pop)
        const truck_end = bridge.shift()
        // (5)
        count_pop += truck_end !== 0 ? 1 : 0
        weight_current -= truck_end
        time++
    }
    return time
}

 

idea: 배열을 통해서 shift(), push()를 통해 queue처럼 활용.

(1) time: return 값, weight_current: 다리 위의 현재 무게, count_pop: 다리를 다 건넌 차의 수

    bridge: 다리 길이만큼 선언, count_truck: 트럭의 수

(2) 다리를 다 건넌 트럭의 수가 건너기 전 수와 같아지면 stop!

(3) if: weight_current에서 앞으로 건널 트럭 무게와 다리를 건널 트럭의 무게를 계산해준 것이 견딜 수 있다면,

    트럭을 건널 수 있게 해줍니다. (shift)

    else: (생략과 같지만, pop이 0으로 선언되어 있으므로, 건너지 못한것과 같습니다.)

(4) pop된 차의 무게 (0 or 차의 무게)를 weight_current에 더 해주고, 다리에 push 해줍니다.

     그리고 truck_end 선언을 통해 다리의 끝에 있는 차가 완벽히 건널 수 있도록 해줍니다.

   ** pop이 되었으면 차가 건너는 것, 아니라면 0을 푸시하는게 헷갈리지 않도록 합니다. shift()도 마찬가지

(5) truck_end의 무게가 0이 아니라면 빠져나온 트럭의 수를 추가해줍니다.

     weight_current의 무게도 마찬가지로 빠져나온 트럭의 무게만큼 감소시켜줍니다.

     time 1이 증가되었습니다.

그리고 return!