[Javascript][Programmers] 다리를 지나는 트럭

 

문제

이 문제는 트럭이 순차적으로 다리를 건너며, 다리 위에서의 트럭 상태(시간, 무게)를 관리해야 하는 점이 핵심입니다. 트럭을 순차적으로 처리해야하는 점을 고려하면 큐를 사용하는 것이 적합합니다.

 

나의 풀이

function solution(bridge_length, weight, truck_weights) {
    let time = 0; // 경과 시간
    let bridgeQueue = []; // 다리 위의 트럭 상태 관리 (트럭 무게와 남은 시간을 관리)
    let bridgeWeight = 0; // 현재 다리 위에 있는 트럭들의 무게 합

    while (truck_weights.length > 0 || bridgeQueue.length > 0) {
        time++;

        // 다리에서 트럭이 나갈 시간인지 확인
        if (bridgeQueue.length > 0 && bridgeQueue[0].time === time) {
            bridgeWeight -= bridgeQueue.shift().weight;
        }

        // 다음 트럭이 다리에 올라갈 수 있는지 확인
        if (truck_weights.length > 0 && bridgeWeight + truck_weights[0] <= weight) {
            const truckWeight = truck_weights.shift();
            bridgeWeight += truckWeight;
            bridgeQueue.push({ weight: truckWeight, time: time + bridge_length });
        }        
    }

    return time;
}

시간을 1씩 증가시키면서 각 단계마다 다리를 완전히 건넌 트럭을 제거하고, 대기 중인 트럭이 다리에 올라갈 수 있는지(무게) 확인합니다. 가능하다면 새 트럭을 다리에 추가하고, 그 트럭이 다리를 건너는 예상 시간을 계산합니다. 이 과정을 모든 트럭이 다리를 건널 때까지 반복합니다.

 

문제점

다음 두 조건이 동시에 충족될 때 알고리즘의 비효율성이 발생합니다:

1. 다리 위의 선두 트럭이 아직 다리를 완전히 건너지 못했을 때
2. 대기 중인 다음 트럭이 다리의 중량 제한으로 인해 진입할 수 없을 때

이러한 상황에서 알고리즘은 의미 있는 변화 없이 단순히 시간만 증가시키며 반복문을 계속 실행합니다.

 

이 문제를 해결하기 위해서는 이런 '정체' 상황을 감지하고, 다음 의미 있는 이벤트(트럭의 진출 또는 진입)가 발생할 때까지 시간을 한 번에 건너뛰는 최적화 방법을 고려해볼 수 있습니다.

 

다른 풀이

위의 코드에 시간을 건너뛰는 조건문을 하나 추가하였습니다. 이를 통해 앞서 언급한 '정체' 상황을 효과적으로 해결할 수 있습니다.

function solution(bridge_length, weight, truck_weights) {
    let time = 0;
    let bridgeQueue = [];
    let bridgeWeight = 0;

    while (truck_weights.length > 0 || bridgeQueue.length > 0) {
        time++;

        if (bridgeQueue.length > 0 && bridgeQueue[0].time === time) {
            bridgeWeight -= bridgeQueue.shift().weight;
        }

        if (truck_weights.length > 0 && bridgeWeight + truck_weights[0] <= weight) {
            const truckWeight = truck_weights.shift();
            bridgeWeight += truckWeight;
            bridgeQueue.push({ weight: truckWeight, time: time + bridge_length });
        } else if (bridgeQueue.length > 0) {
            // 다음 트럭이 다리에 올라갈 수 없는 경우, 가장 빨리 나갈 트럭의 시간으로 점프
            time = bridgeQueue[0].time - 1;
        }
    }

    return time;
}

 

해당 위치에 트럭이 없음을 의미하는 0을 이용하여 해결할 수도 있습니다.

function solution(bridge_length, weight, truck_weights) {
    let time = 0;
    let bridge = Array(bridge_length).fill(0);
    let current_weight = 0;

    while (truck_weights.length > 0 || current_weight > 0) {
        time++;

        // 다리에서 나가는 트럭 처리
        current_weight -= bridge.shift();

        if (truck_weights.length > 0) {
            // 다음 트럭이 다리에 올라갈 수 있는 경우
            if (current_weight + truck_weights[0] <= weight) {
                let truck = truck_weights.shift();
                bridge.push(truck);
                current_weight += truck;
            } else {
                // 다리에 올라갈 수 없는 경우 0을 추가
                bridge.push(0);
            }
        } else {
            // 남은 트럭이 없는 경우 0을 추가
            // 문제를 해결하는데는 불필요하지만 다리의 길이를 유지하기 위해 사용
            bridge.push(0);
        }
    }

    return time;
}

 

---

Reference

[Programmers] 다리를 지나는 트럭 > 다른 사람의 풀이