[프로그래머스] Queue "다리위를 건너는 트럭" 풀이 과정

프로그래머스 자료구조 큐 문제인 다리위를 건너는 트럭이라는 문제 풀이 과정을 공유해 보려합니다.

레벨 2 문제 링크

문제 해설

주어진 값

• bridge_length : 다리에 올라갈 수 있는 트럭 (숫자형)
• weight : 다리가 견딜 수 있는 무게 (숫자형)
• truck_weights : 트럭별 무게 (배열)

구해야하는 값

• 모든 트럭이 다리를 건널때 까지 걸리는 시간(초단위)

문제 이해를위해 추가로 알아야할 점

• 다리에 오르지 않은 트럭은 무시한다.
• 트럭은 주어진 배열(truck_weights) 순서대로 건너야 한다. 즉, 0번째 트럭이 다리를 건너기 전까지, 다음 트럭은 다리를 건널 수 없다.

다음으로, 문제에서 설명이 부족해서 이해하기 어려웠던점은 다음과 같습니다. 주어진 값 bridge_length라는 이름을 보고 이해해야 합니다.

• 트럭 한대가 다리를 지나가는데 걸리는 시간은 bridgh_length이다.
• 즉, 트럭은 1초당 1 length만큼 이동할 수 있다.

문제에 주어진 예시가 처음엔 잘 이해가 안갔는데, 위에 설명이 부족했던 탓이였어요. (이부분은 프로그래머스측에서 문제 보완을 해주셨으면 좋겠네요.)

예시 설명

문제에 설명된 예시를 조금 더 쉽게 이해해 봅시다.

주어진 조건이 다음과 같다고 가정합시다.
bridge_weight: 2
weight : 10
truck_weights : [7,4,5,6]

4개의 트럭은 다리위에 최대 2대까지 올라갈 수 있고, 총 무게가 10kg를 넘으면 안되는 다리를 건너야 합니다.

0초일때
모든 트럭은 다리를 건널 준비를 합니다.

1초일때

• 다리를 건너고 있는 트럭이 없습니다.
• 첫번째 트럭은 총 무게 10을 넘지 않습니다.
• 다리를 건넙니다.

2초일때

• 첫번째 트럭이 다리를 건넌지 1초가 지났습니다.
• 다리를 건널 수 있는 트럭의 수는 총 2대이므로 한대가 더 건널 수 있는지 확인합니다.
• 다음 건너야 하는 트럭(4)이 다리를 건널 경우 총 무게 10이 넘기 때문에 대기합니다.

3초일때

• 첫번째 트럭은 다리를 건넌지 2초가 되어 다리를 빠져 나갑니다.
• 다리를 건너고 있는 트럭은 0이기때문에 다음 트럭(4)가 다리에 진입합니다.

4초일때

• 두번째 트럭(4)가 다리를 건넌지 1초가 경과했습니다.
• 세번째 트럭(5)가 건널수 있는지 판별합니다.
• 현재 한대 더 다리에 오를 수 있고 다리에 오를 수 있는 남은 무게는 6이기 때문에 세번째 트럭이 다리에 오릅니다.

5초일때

• 두번째 트럭(4)가 다리를 건넌지 2초가 되어 다리를 빠져나갑니다.
• 세번째 트럭(5)는 다리를 건넌지 1초가 경과했습니다.
• 네번째 트럭(6)은 다리를 건널수 있는지 판별합니다.
• 1대 더 오를 수 있지만 남은 무게가 5이기때문에 무게가 6인 트럭은 대기합니다.

6초일때

• 세번째 트럭(5)는 다리를 건넌지 2초가 되어 다리를 빠져나갑니다.
• 네번째 트럭(6)이 다리를 건널수 있는지 판별합니다.
• 다리를 건너고 있는 트럭이 없기때문에 네번째 트럭은 다리에 진입합니다.

7초일때

• 네번째 트럭이 다리를 건넌지 1초가 지났습니다.

8초일때

• 네번째 트럭이 다리를 건넌지 2초가 되어 다리를 빠져나갑니다.

즉, 이 트럭들이 다리를 지나가는데 걸리는 최소 시간은 8초가 됩니다.

위 문제 해설에서 아래와 같은 내용들이 반복되고 있습니다.

• 1초가 지날때 마다,
• 현재 다리위에 있는 트럭이 몇초가 지났는지 확인합니다.
• 2초(bridge_length)가 지나면 다리를 다 건넌걸로 간주 합니다.
• 대기중인 트럭을 다리위에 진입시키기 위해 아래 두가지 사항을 확인합니다.
• 현재 다리에 2대(bridge_length)가 차있다면, 차는 다음 기회를 기다려야 합니다.
• 2대가 다 차있지 않더라도, 지나가야하는 트럭의 무게가 다리에 오를수 있는 여유가 되는지 확인합니다.

문제 해결

트럭이 다리에 오르고 다리에 오른 순서대로 빠져나가야 하기 때문에, 이 문제는 큐(Queue)라는 자료구조를 이용합니다.
그렇다면, enQueue(다리에 진입시키고), deQueue(다리에서 빠져나가는) 조건은 어떻게 될까요?

enQueue조건

• 대기중인 트럭의 무게 <= 최대 오를수 있는 트럭의 무게 - 현재 다리위에 있는 모든 트럭의 무게 합 (작거나 같음)
• 남은 수용 무게를 매번 계산하지 않는 방법 : enQueue할때 마다, 현재 다리위에 있는 트럭의 무게를 누적해서 더한다.

deQueue 조건

• 다리위에 있는 트럭중 맨 첫번째 트럭이 진입한 시간을 enQueue시 기록해 두고
• 현재 시간 - 트럭이 진입한 시간이 bridge_length 이상인지 확인한다.
• bridge_length이상이면, deQueue한다.
• enQueue시 누적해 두었던 트럭의 무게에서 빠져나간 트럭의 무게를 뺀다.

위 조건을 고려하여 작성된 코드는 다음과 같습니다.

function solution(bridge_length, weight, truck_weights) {
	
    let time = 0; // 몇초가 지났는지 기록한다.
    let passedCount = 0; // 현재 다리를 건넌 트럭의 갯수
    
    const waitingTrucks = [...truck_weights]; // 대기중인 트럭 배열
    const passingQueue = []; // 다리를 건너고 있는 트럭 배열
    
    let currentWeight = 0; // 다리위에 있는 트럭의 무게 합
    
    while(passedCount < truck_weights.length) {
        // deQueue 조건
        if(passingQueue.length > 0 && time - passingQueue[0] === bridge_length) {
            passingQueue.shift()
            currentWeight -= truck_weights[passedCount]
            passedCount += 1;
        }
        
        // enQueue 조건
        const restWeight = weight - currentWeight;

        if(restWeight >= waitingTrucks[0]) {
            const truck = waitingTrucks.shift();
            currentWeight += truck;
            passingQueue.push(time)
        }
        
        time++;
    }
    
    return time;
}

결론

결론적으로, 이 문제는 다리를 건너는 트럭들의 상태를 관리하기 위해 큐(Queue) 자료구조를 활용하는 것이 중요하다고 생각합니다.
enQueue 조건은 대기 중인 트럭의 무게가 다리의 최대 수용 무게에서 현재 다리 위에 있는 트럭들의 무게 합을 뺀 값보다 작거나 같을 때입니다. 이를 계산하기 위해 enQueue할 때마다 현재 다리 위의 트럭 무게를 누적하여 관리합니다.
deQueue 조건은 다리 위에 있는 트럭 중 맨 앞의 트럭이 다리에 진입한 시간과 현재 시간의 차이가 다리의 길이(bridge_length) 이상일 때입니다. 이를 위해 enQueue 시점에 트럭이 진입한 시간을 기록해두고, 현재 시간과 비교하여 deQueue 여부를 판단하면 쉽게 풀수 있습니다.

코드의 시간 복잡도는 O(n)입니다. 여기서 n은 트럭의 개수를 의미합니다. 코드에서 while 루프는 모든 트럭이 다리를 건너기 전까지 반복되므로, 트럭의 개수에 비례하여 루프가 실행됩니다.