택배 배달과 수거하기

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

프로그래머스

택배 배달과 수거하는 과정을 만족하면서 최소 이동 거리를 구하는 문제이다.

 

택배 배달과 수거하는 과정은 배달을 끝내고 수거를 하는 과정에 연속이며,

택배를 배달하면서 이동한 거리만큼은 다시 물류센터로 돌아오기 때문에 수거하는 과정을 같이 진행할 수 있다.

 

모든 집에 배달 및 수거를 진행하기 위한 순회 ( N ) 과 집 마다 배달 및 수거를 분배하는 순회 ( N ) 이 요구된다.

O ( N^2 ) 에 해결할 수 있는 문제이다.

 

택배 배달 또는 수거를 하기 위해 가장 먼 거리의 집을 찾고 이동하면서 Cap 만큼의 행동을 소비한다.
* 배달이 끝나면 수거도 자연스럽게 Cap 만큼 수행할 수 있다

// it is not supported below node 18.
function findLastIndex(arr, selector, n) {
    if(n === undefined) n = arr.length;

    for (var i = n - 1; i >= 0; i--) {
        if (selector(arr[i])) return i;
    }
    
    return -1;
}

function solution(cap, n, deliveries, pickups) {
    var answer = 0;

    // find first index that visit home nearest from last.
    var idx_delivery = findLastIndex(deliveries, e => e > 0, n);
    var idx_pickup = findLastIndex(pickups, e => e > 0, n);

    // Satisfy all conditions that end of delivery and pickup - O(N)
    while (idx_delivery > -1 || idx_pickup > -1) {
        var deliveryCap = cap;
        var pickupCap = cap;

        var dist = Math.max(idx_delivery, idx_pickup);
        // dist is "index + 1" and round is "multiply 2".
        answer += (dist + 1) * 2;

        // check "extra cap" and index
        while (deliveryCap > 0 && idx_delivery > -1) {
            if (deliveryCap > deliveries[idx_delivery]) {
                deliveryCap -= deliveries[idx_delivery];
                deliveries[idx_delivery] = 0;
            } else {
                deliveries[idx_delivery] -= deliveryCap;
                deliveryCap = 0;
            }
            // pull current index to left
            // this is "0" ( no more ) home be skiped
            for(;deliveries[idx_delivery] == 0 && idx_delivery > -1; idx_delivery--);
        }
        // same about "delivery"
        while (pickupCap > 0 && idx_pickup > -1) {
            if (pickupCap > pickups[idx_pickup]) {
                pickupCap -= pickups[idx_pickup];
                pickups[idx_pickup] = 0;
            } else {
                pickups[idx_pickup] -= pickupCap;
                pickupCap = 0;
            }

            for(;pickups[idx_pickup] == 0 && idx_pickup > -1; idx_pickup--);
        }
    }
    
    return answer;
}