[TIL #19] 다리를 지나는 트럭

https://school.programmers.co.kr/learn/courses/30/lessons/42583

프로그래머스

 

열린계에선 당연히 선박이 다리 위에 오기 전부터 그 무게는 교량에 반영돼있다

 

이 문제를 보고 위의 이미지부터 떠올랐다.

열린계라고 생각했을 때, 늘어나는 무게는 없다고 해도 될 정도로 미미하다.

하지만 물의 무게는 여전히 크다.

이걸 잘 생각하면서 다리를 만들어야 한다.

이건 우리가 일상적으로 차량을 통해 이용하는 다리에도 적용되는 개념이다.

 

이 문제는 그러한 다리의 한계 하중을 초과하지 않고 어떻게 트럭을 다 반대편으로 옮길지 고민하는 문제.

모든 트럭을 보내기 위해 최소 몇 사이클이 소요되는지 확인해야 한다.

 

일단 다리의 길이는 유한한 배열로 생각할 수 있다.

트럭이 이 다리를 한 사이클 만에 건널 수 없고, 사이클마다 1씩 움직인다.

만약 다리가 매우 길다면?

사이클마다 그 배열을 고치는 것 자체가 일이다.

어차피 트럭이 다리에 올라타는 순간 걸리는 시간 자체는 정해져 있다.

그 무의미한 시간과 연산을 우리는 그냥 건너뛸 수 있다.

 

1. 먼저 다리 건너기가 끝난 트럭이 있는지 확인한다
    - 있다면 큐(다리)에서 제거.
2. 다음 트럭을 다리에 올릴 수 있는지 확인한다
    - 한계 중량을 초과했는지도 확인해야 한다.
3. 중량에 여유가 있으면 트럭을 큐에 넣는다.
4. 만약 트럭이 없거나 중량을 초과했다면 시간을 건너뛴다
    - 어차피 트럭이 건너는 시간은 정해져 있기에 그런 시간은 다 날릴 수 있다.

 

이걸 옮기면 다음과 같다.

function solution(bridgeLength, weight, truckWeights) {
    let time = 0; // 총 걸린 시간
    let bridgeQueue = []; // 다리를 건너는 트럭들을 저장하는 큐 (트럭의 무게와 exitTime을 저장)
    let currentWeight = 0; // 현재 다리에 올라온 트럭들의 총 무게
    let trucks = truckWeights.reverse(); // 대기 중인 트럭들을 역순으로 정렬하여 pop()으로 처리

    while (bridgeQueue.length > 0 || trucks.length > 0) {
        time += 1;

        // 다리를 완전히 건넌 트럭이 있는지 확인
        if (bridgeQueue.length > 0 && bridgeQueue[0].exitTime === time) {
            let exitedTruck = bridgeQueue.shift();
            currentWeight -= exitedTruck.weight;
        }

        // 다음 트럭을 다리에 올릴 수 있는지 확인
        if (trucks.length > 0) {
            let nextTruckWeight = trucks[trucks.length - 1];
            if (currentWeight + nextTruckWeight <= weight) {
                let truckWeight = trucks.pop();
                bridgeQueue.push({ 
                    weight: truckWeight, 
                    exitTime: time + bridgeLength 
                });
                currentWeight += truckWeight;
            }
        }

        // 만약 다리에 올릴 트럭이 없거나 무게 제한으로 추가하지 못했다면, 시간을 건너뛰기 위해 다음 트럭의 exitTime으로 이동
        if (bridgeQueue.length > 0 && trucks.length > 0 && currentWeight + trucks[trucks.length - 1] > weight) {
            // 다음 트럭이 올라갈 수 있는 시간으로 시간을 빠르게 이동
            let nextExitTime = bridgeQueue[0].exitTime;
            time = Math.max(time, nextExitTime - 1);
        }
    }

    return time;
}

 

 

처음엔 이런 방법을 생각했다.

다리 길이만큼의 0으로 채운 배열을 만들고 이를 다리의 현 상태라고 가정한다.

다리의 빈칸을 0으로 정의한다.

한 땀 한 땀 사이클을 돌며 걸린 시간을 계산한다.

 

function solution(bridgeLength, weight, truckWeights) {
    let time = 0;
    let bridge = Array(bridgeLength).fill(0);
    let currentWeight = 0;
    let trucks = truckWeights.reverse(); // 대기 중인 트럭들을 역순으로 정렬 -> shift() 사용을 피하기 위해

    while (bridge.length > 0) {
        time += 1;

        // 다리의 앞부분에서 트럭을 제거하고 현재 무게를 조정
        let exited = bridge.shift();
        currentWeight -= exited;

        // 다음 트럭을 다리에 올릴 수 있는지 확인
        if (trucks.length > 0) {
            let nextTruckWeight = trucks[trucks.length - 1]; // 대기열의 첫 번째 트럭
            if (currentWeight + nextTruckWeight <= weight) {
                let truckWeight = trucks.pop();
                bridge.push(truckWeight);
                currentWeight += truckWeight;
            } else {
                bridge.push(0); // 트럭을 올릴 수 없으면 0을 추가하여 시간만 증가
            }
        }
    }

    return time;
}

통과가 안 되는 것은 아니다.

다리 길이와 트럭의 개수 모두 1 이상 10000 이하였기 때문.

하지만 둘의 시간을 비교하면 큰 차이가 있다.

 

불필요한 시간을 생략하는 방식.

 

그냥 사이클을 돌리는 방식.

 

특히 5번 케이스에서 이 차이가 두드러진다.

나중에 이런 사소한 퍼포먼스 차이가 어떤 일을 야기할지 알 수가 없으니

최적화에 대한 고민이 필요할 것이다.