[JavaScript] 다리를 지나는 트럭 - 스택/큐

프로그래머스 알고리즘 고득점 Kit

 

문제 설명

 
트럭 여러 대가 강을 가로지르는 일차선 다리를 정해진 순으로 건너려 합니다. 모든 트럭이 다리를 건너려면 최소 몇 초가 걸리는지 알아내야 합니다. 다리에는 트럭이 최대 bridge_length대 올라갈 수 있으며, 다리는 weight 이하까지의 무게를 견딜 수 있습니다. 단, 다리에 완전히 오르지 않은 트럭의 무게는 무시합니다. 예를 들어, 트럭 2대가 올라갈 수 있고 무게를 10kg까지 견디는 다리가 있습니다. 무게가 [7, 4, 5, 6]kg인 트럭이 순서대로 최단 시간 안에 다리를 건너려면 다음과 같이 건너야 합니다.
 

예시 - 다리를 지나는 트럭

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

---

문제 풀이

 

1. 초기화

let time = 0;
let bridgeQueue = Array(bridge_length).fill(0);
let currentWeight = 0;

 
설명:

1. time: 경과 시간을 기록하는 변수입니다.
2. bridgeQueue: 다리를 나타내는 큐입니다. 길이가 bridge_length이며, 초기에는 빈 공간(0)으로 채워져 있습니다.
   • 아이디어: 다리를 큐로 모델링하여, 트럭의 위치와 상태를 효율적으로 관리합니다.
3. currentWeight: 다리 위에 있는 트럭들의 총 무게를 저장합니다.
   • 핵심 개념: 다리는 한 번에 weight 이하의 무게만 견딜 수 있으므로, 현재 다리 위의 무게를 실시간으로 추적해야 합니다.

 

2. 반복문 시작

while (bridgeQueue.length > 0) {
    time++;
    currentWeight -= bridgeQueue.shift();

 
설명:

1. bridgeQueue.length > 0: 다리가 완전히 비어있을 때까지 반복합니다. 즉, 다리 위에 있는 모든 트럭이 건너면 반복문이 종료됩니다.
2. time++: 각 반복은 1초를 나타냅니다.
3. bridgeQueue.shift(): 다리의 맨 앞에 있는 트럭(또는 빈 공간)을 제거합니다. 제거된 트럭의 무게는 currentWeight에서 차감합니다.
   • 핵심 개념: 트럭이 bridge_length만큼 이동하면 다리를 완전히 건넌 것으로 처리합니다.

 

3. 트럭 추가 여부 확인

if (truck_weights.length > 0) {
    if (currentWeight + truck_weights[0] <= weight) {
        let truck = truck_weights.shift();
        bridgeQueue.push(truck);
        currentWeight += truck;
    } else {
        bridgeQueue.push(0);
    }
}

 
설명:

1. 대기 트럭이 있는 경우(truck_weights.length > 0):
   • 트럭이 다리에 올라갈 수 있는 조건을 확인합니다.
2. currentWeight + truck_weights[0] <= weight:
   • 현재 다리 위의 무게와 다음 트럭의 무게를 더한 값이 weight 이하인지 확인합니다.
   • 핵심 개념: 다리가 견딜 수 있는 무게를 초과하지 않도록 트럭의 진입 여부를 결정합니다.
3. 트럭 추가:
   • 조건이 만족되면, truck_weights에서 트럭을 꺼내 bridgeQueue에 추가하고, currentWeight를 업데이트합니다.
4. 빈 공간 추가:
   • 조건이 만족되지 않으면, 다리 큐에 빈 공간(0)을 추가합니다. 이는 "트럭이 이동하지 않은 1초"를 나타냅니다.

 

4. 종료 조건

return time;

 
설명:

• 반복문이 종료되면, 모든 트럭이 다리를 건넌 상태이며, 경과 시간을 반환합니다.

 

---

 

부가 설명: 큐(queue)의 활용

1. 다리를 큐로 모델링:
   • 다리를 큐로 표현하여, 트럭이 다리를 건너는 과정을 시뮬레이션합니다.
   • 트럭이 이동할 때마다 맨 앞 트럭을 제거하고 새로운 트럭(또는 빈 공간)을 뒤에 추가하는 방식은 FIFO(First-In-First-Out) 구조와 동일합니다.
2. 효율성:
   • bridgeQueue의 크기는 항상 bridge_length로 고정되어 있으므로, 트럭 수에 관계없이 일정한 메모리와 연산 시간을 유지합니다.

 

---

 

핵심 아이디어 정리

1. 다리의 이동을 큐로 모델링:
   • 트럭이 다리를 건너는 과정을 "고정된 크기의 큐"로 구현하여 시간 경과와 트럭의 이동을 직관적으로 처리합니다.
2. 무게 제한 관리:
   • currentWeight를 실시간으로 업데이트하여, 무게 제한을 초과하지 않도록 트럭의 진입 여부를 동적으로 결정합니다.
3. 시간 경과 시뮬레이션:
   • 매 반복마다 1초가 경과하도록 시뮬레이션하며, 트럭이 이동하지 못할 때는 빈 공간(0)을 추가하여 시간을 조정합니다.