[알고리즘/프로그래머스/카카오] 택배 배달과 수거하기

문제

---

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

프로그래머스

 

풀이

---

트럭에 최대 cap개의 택배를 실을 수 있고, 집마다 배달/수거할 택배 상자의 개수가 있을 때, 모든 택배를 처리할 수 있는 최소 이동 거리를 구하는 문제이다. 

배달/수거가 필요한 가장 먼 지점까지 이동하고, 이후 초기 지점으로 돌아와야 하기 때문에 이동 거리는 Math.max(배달 최대 거리, 수거 최대 거리)의 2배가 된다.

deliveryP와 pickupP는 각각 배송/수거해야하는 지점이다. 이때 배열의 값이 0인 경우, 트럭이 갈 필요가 없으므로 시작 포인터를 배열의 가장 끝에서 0이 아닌 지점까지 이동해야 한다.  예를 들어, deliveries = [1, 0, 3, 1, 2]이고, pickups = [0, 2, 0, 4, 0]이라면 deliveryP는 4, pickupP는 3으로 설정한다. 

배달과 수거하는 과정은 사실상 동일한 로직을 사용한다. boxes는 배달/수거 배열이고, currentCnt는 현재 트럭에 실은 택배 상자의 개수, currentPointer는 배달/수거 시작 지점, 그리고 cap은 트럭에 최대 실을 수 있는 개수이다. 배열 뒤쪽에서 앞으로 돌면서 currentPointer에서 시작해 해당 집에 있는 모든 택배를 배달/수거할 수 있는지 확인한다. 한 번에 가능한 경우, 트럭에 싣고(currentCnt += boxes[i]), 해당 집에서 택배 상자를 제거하고(boxes[i]), 포인터를 앞으로 이동한다(currentPointer -= 1). 한 번에 다 실을 수 없는 경우, 실을 수 있는 만큼(cap-currentCnt)만 싣고, 다음 시작점이 될 수 있도록 포인터는 현재 집으로 옮겨준(currentPointer = i) 다음, 집마다 실을 수 없으므로 break한다. 

이렇게 이동한 포인터를 반환해 둘 중 하나라도 0 이상일 때 계속 반복하면서 minDistance를 구한다.

function doWork(boxes, currentCnt, currentPointer, cap) {
    for (let i=currentPointer;i>=0;i--) {
        // 모두 배달/수거 가능한 경우
        if (currentCnt + boxes[i] <= cap) {
            currentCnt += boxes[i]
            boxes[i] = 0
            currentPointer -= 1
        } else {
            // 일부만 가능한 경우(더 이상 적재 불가하므로 break)
            boxes[i] -= cap - currentCnt
            currentPointer = i
            break
        }
    }
    
    return currentPointer
}


function solution(cap, n, deliveries, pickups) {
    /**
        각 포인터가 유효할 때까지 loop
        while문 돌면서 뒤에서부터 제거해나간다.
        한 루프에 배달/수거 최대로 제거하고 Math.max(배달 최대 거리, 수거 최대 거리) * 2    
    */
    let deliveryP = n-1
    let pickupP = n-1
    let minDistance = 0
    
    while (deliveryP >= 0 || pickupP >= 0) {
        let deliveryCnt = 0
        let pickupCnt = 0
     
        // 배열 끝 기준 0이 아닌 인덱스에서 시작
        while (deliveries[deliveryP] === 0) {
            deliveryP -= 1
        }
        
         while (pickups[pickupP] === 0) {
            pickupP -= 1
        }
        
        // 거리 계산
        minDistance += Math.max(deliveryP + 1, pickupP + 1) * 2

        // 배달
        deliveryP = doWork(deliveries, deliveryCnt, deliveryP, cap)
        
        // 수거
        pickupP = doWork(pickups, pickupCnt, pickupP, cap)     
    }
    
    return minDistance
}