[프로그래머스] 2023 KAKAO BLIND RECRUITMENT > 택배 배달과 수거하기 (javascript)

문제 링크 : https://school.programmers.co.kr/learn/courses/30/lessons/150369

 

문제

[한 트럭에 실을 수 있는 상자 수] [총 집 수] [각 집에 배달할 갯수] [각 집에서 수거할 갯수] 를 input 으로 받아

[모든 상자를 배달하고 모든 빈 상자를 수거하는 최단거리] 를 구하는 문제이다.

물류창고에서 상자를 싣고 빈 상자를 내려놓을 수 있으며, 왕복은 여러 번 할 수 있다.

n개의 각 집은 물류창고로 부터 [1, 2, 3, ....., n] 의 거리이며 인접한 두 집 간의 거리는 1 이다.

 

문제 원본을 보려면 아래를 펼쳐 보자.

---

풀이

입출력 예시에 힌트가 전부 나와 있다.

 

트럭에 상자를 cap 만큼 싣고 가장 먼 집 까지 배달했다가,

 

빈 상자를 수거할 가장 먼 집 부터 cap 만큼 상자를 수거해 오면 된다.

 

'배달 할 집 중 가장 먼 곳' 과 '빈 상자를 수거할 집 중 가장 먼 곳' 의 거리 중 더 먼 곳을 왕복 거리로 하면 된다.

(answer += (endIdx+1) * 2 // 왕복이므로 곱하기 2 해 준다.)

 

1. '배달 할 집 중 가장 먼 곳' 과 '빈 상자를 수거할 집 중 가장 먼 곳' 의 거리 중 더 먼 곳 구하기

pickFinIdx = findNewFinIdx(pickFinIdx, pickups);
deliverFinIdx = findNewFinIdx(deliverFinIdx, deliveries);

let endIdx = Math.max(pickFinIdx, deliverFinIdx);

현 시점에서 배달 / 수거 할 가장 먼 집을 구하는 메서드인 findNewFinIdx 는 같은 로직이므로 하나의 메서드를 공유한다.

로직을 보면 알 수 있지만, 항상 '뒤 부터' 어느 집이 가장 먼 집인지 찾는다.

function findNewFinIdx(finIdx, arr) {
    for(let i=finIdx; i>=0; i--) {
        if(arr[i] > 0) {
            return i;
        }
    }
    return -1;
}

 

2. 이 때, endIdx 가 -1 이라면, 모든 집의 배달 및 수거가 끝난 것이므로 loop 를 종료하면 된다.

if(endIdx == -1) {
    break;
}

3. 배달과 수거를 한다.

process(deliverFinIdx, deliveries, delivered, cap);
process(pickFinIdx, pickups, picked, cap);

배달 / 수거 하는 로직 또한 동일하기에 같은 메서드를 공유한다.

로직을 보면 뒤에서 부터 배달 / 수거 를 하는 것으로 보인다.

'배달 순서' 가 거꾸로 된 것은 계산 로직을 간편하게 하기 위함이다.

 

'현실 세계' 에선

'뒤에서 k 개의 집 중 가장 첫 번째 집 부터 배달' 하고

'맨 뒷 집 부터 빈 상자를 수거' 한다고 생각하면 된다.

function process(finIdx, arr, cnt, cap) {
    for(let i=finIdx; i>=0; i--) {
        if(arr[i] == 0) continue;

        if(cap == cnt) break;

        if(cnt + arr[i] <= cap) {
            cnt += arr[i];
            arr[i] = 0;
        }else {
            let rest = cap - cnt;
            cnt += rest;
            arr[i] -= rest;
        }
    }
    return cnt;
}

 

4. 배달/수거 가 끝나고 물류센터까지 돌아 온 거리를 answer 에 합산한다.

answer += (endIdx+1) * 2;

---

예외상황

1. 배달 및 수거할 곳이 처음부터 없는 경우

0 을 return 하면 된다.

---

전체 코드 

function solution(cap, n, deliveries, pickups) {
    var answer = 0;
    //1. 픽업할 곳 중 가장 먼 곳(idx로 기억)
    //2. 배달 할 곳 중 가장 먼 곳(idx로 기억)
    // 1,2 중 더 먼 곳 까지 갔다 오기 (answer + idx*2)
    let pickFinIdx = pickups.length-1;
    let deliverFinIdx = deliveries.length-1;
    
    while(true) {
        let picked = 0;
        let delivered = 0;
        
        pickFinIdx = findNewFinIdx(pickFinIdx, pickups);
        deliverFinIdx = findNewFinIdx(deliverFinIdx, deliveries);
        
        let endIdx = Math.max(pickFinIdx, deliverFinIdx);
        
        if(endIdx == -1) {
            break;
        }
        
        process(deliverFinIdx, deliveries, delivered, cap);
        process(pickFinIdx, pickups, picked, cap);
        
        answer += (endIdx+1) * 2;
    }
    
    return answer;
}

function findNewFinIdx(finIdx, arr) {
    for(let i=finIdx; i>=0; i--) {
        if(arr[i] > 0) {
            return i;
        }
    }
    return -1;
}

function process(finIdx, arr, cnt, cap) {
    for(let i=finIdx; i>=0; i--) {
        if(arr[i] == 0) continue;

        if(cap == cnt) break;

        if(cnt + arr[i] <= cap) {
            cnt += arr[i];
            arr[i] = 0;
        }else {
            let rest = cap - cnt;
            cnt += rest;
            arr[i] -= rest;
        }
    }
    return cnt;
}