[프로그래머스] 택배 배달과 수거하기 Lv2 JAVA [KAKAO][DP][STACK][엄탱]

문제 링크

프로그래머스

문제 설명

예시

당신은 일렬로 나열된 n개의 집에 택배를 배달하려 합니다. 배달할 물건은 모두 크기가 같은 재활용 택배 상자에 담아 배달하며, 배달을 다니면서 빈 재활용 택배 상자들을 수거하려 합니다.
배달할 택배들은 모두 재활용 택배 상자에 담겨서 물류창고에 보관되어 있고, i번째 집은 물류창고에서 거리 i만큼 떨어져 있습니다. 또한 i번째 집은 j번째 집과 거리 j - i만큼 떨어져 있습니다. (1 ≤ i ≤ j ≤ n)

트럭에는 재활용 택배 상자를 최대 cap개 실을 수 있습니다. 트럭은 배달할 재활용 택배 상자들을 실어 물류창고에서 출발해 각 집에 배달하면서, 빈 재활용 택배 상자들을 수거해 물류창고에 내립니다. 각 집마다 배달할 재활용 택배 상자의 개수와 수거할 빈 재활용 택배 상자의 개수를 알고 있을 때, 트럭 하나로 모든 배달과 수거를 마치고 물류창고까지 돌아올 수 있는 최소 이동 거리를 구하려 합니다. 각 집에 배달 및 수거할 때, 원하는 개수만큼 택배를 배달 및 수거할 수 있습니다.

다음은 cap=4 일 때, 최소 거리로 이동하면서 5개의 집에 배달 및 수거하는 과정을 나타낸 예시입니다.

해설

어떤 방법으로 풀어야 할지 결정하기 전에 해당 문제의 특징을 짚고 넘어가면 좋을 것 같습니다.

 

첫째, 이동 거리는 물류창고에서 집으로 가는 거리, 집에서 물류창고로 돌아오는 거리 존재합니다. 분명, 당연한 내용이지만 저는 순간 착각해서 가는 거리만 계산해 주는 실수를 범했습니다.. 

 

둘째, 최소 이동 거리를 구하기 위해 가장 먼 거리의 집부터 해결해줘야 합니다. 앞에서부터 해결을 하게 되면 무의미하게 이동거리가 증가하게 됩니다. 예를 들어 cap = 4이고, 첫 번째 집 배달할 택배가 1개이고 두 번째 집이 2개이고 세 번째 집이 1개면, 뒤에서부터 해결을 하면 이동거리는 6이면 완료가 되지만 앞에부터 하게 되면, 12가 걸리게 됩니다. 고로 뒤에부터 해결을 해주는 게 좋습니다.

 

다음으로는 어떤 자료구조, 어떤 알고리즘을 사용하는 게 좋을지 고민이 됩니다.

자료구조, Stack 활용

Stack을 이용한 풀이입니다. 이유는, '후입선출' 특징을 이용하여 가장 맨 뒤에 있는 집을 가져오기 위함입니다. 또한,  '후입선출' 특징에 의해 다시 넣더라도 맨 뒤에 집을 가져올 수 있기 때문입니다.

제가 풀이한 방식은 아래와 같습니다.

 

1. 총 두 개의 Stack 자료구조 준비

• 제가 생각한 최선의 방법은 Stack을 두 개 준비하는 것이었습니다. 
• Stack을 하나만 두고 활용한다면, 배송, 수거를 효율적으로 관리할 수 없다고 생각했습니다.
• 참고로 Stack의 제네릭 함수에 들어갈 객체 타입은 몇 번째 집인지 알 수 있는 Integer로 충분합니다.

2. 배송과 수거할 집들의 위치 Stack에 넣기

• '후입선출'의 특징을 이용해야 하기 때문에, 1번 집부터 순서대로 넣어줬습니다.
• 배송 혹은 수거 택배가 0인 경우에는 넣어주지 않아도 됩니다.

3. 이동거리를 계산해 주자

• 한번 배송, 수거할 때 총 이동 거리는 최대 이동거리 * 2입니다.
• 이동거리를 계산하기 위해 3가지의 경우를 알면 좋은데, 표를 한번 살펴보겠습니다.

 

 

현재 택배가 3번째 집의 배송을 완료했다면 배송과 수거의 총 이동거리는 첫 번째 경우에는 8이며, 두 번째 세 번째는 6입니다. 그렇기 때문에 이동거리는 배송과 수거 중에 제일 많은 이동거리의 2배를 해줘야 합니다.

 

3. 배송 먼저 해주고, 수거 처리를 해줍니다.

• 더 쉽게 이해하기 위해, 이 부분은 실제 택배 일을 하여 배송 후에 수거를 진행했습니다.
• 트럭의 최대 cap 만큼 배송을 처리해 주기 위해, Stack에 값을 꺼내오며 cap을 초과하기 전까지 처리해 줍니다.
• 위와 같은 방식으로 최대 cap만큼 수거를 처리해 줍니다.
• 그 후에는 이동거리를 더해주고 나머지 처리해 주면 됩니다.

코드를 살펴보겠습니다. 너무 기네요..

import java.util.Stack;

class Solution {
    public long solution(int cap, int n, int[] deliveries, int[] pickups) {
        long answer = 0;

        Stack<Integer> deliveryStack = new Stack<>();
        Stack<Integer> pickupStack = new Stack<>();

        for (int i = 0; i < n; i++) {
            if (deliveries[i] != 0) {
                deliveryStack.push(i);                
            }

            if (pickups[i] != 0) {
                pickupStack.push(i);  
            }
        }

        int deliveryLength = 0;
        int pickupLength = 0;
        int deliveryCap = cap;
        int pickupCap = cap;

        while (!deliveryStack.isEmpty() || !pickupStack.isEmpty()) {
            deliveryLength = !deliveryStack.isEmpty() ? deliveryStack.peek() + 1 : deliveryLength;

            while (!deliveryStack.isEmpty()) {
                int delivery = deliveryStack.pop();

                if (deliveryCap - deliveries[delivery] > 0) {
                    deliveryCap -= deliveries[delivery];
                    continue;
                } 
                
                if (deliveryCap - deliveries[delivery] == 0) {
                    deliveryCap = 0;
                    break;
                }
                
                deliveries[delivery] -= deliveryCap;
                deliveryStack.push(delivery);
                deliveryCap = 0;
                break;
            }

            pickupLength = !pickupStack.isEmpty() ? pickupStack.peek() + 1 : pickupLength;

            while (!pickupStack.isEmpty()) {
                int pickup = pickupStack.pop();

                if (pickupCap - pickups[pickup] > 0) {
                    pickupCap -= pickups[pickup];
                    continue;
                }
                
                if (pickupCap - pickups[pickup] == 0) {
                    pickupCap = 0;
                    break;
                }
                
                pickups[pickup] -= pickupCap;
                pickupStack.push(pickup);
                pickupCap = 0;
                break;
            }

            answer += 2 * Math.max(pickupLength, deliveryLength);
            pickupLength = 0;
            deliveryLength = 0;
            deliveryCap = cap;
            pickupCap = cap;
        }

        return answer;
    }
}

 

알고리즘, DP 활용

해당 풀이는 제가 생각한 풀이가 아닌, 다른 사람의 풀이를 해석한 풀이인데 너무 괜찮아서 공부해 보았습니다. 다음에 비슷한 문제가 나온다면 Stack보다는 DP 방식을 사용할 것 같습니다.

 

우선, 코드를 살펴보겠습니다.

class Solution {
    public long solution(int cap, int n, int[] deliveries, int[] pickups) {
        long answer = 0;
        int deliver = 0;
        int pickup = 0;
        
        for(int i = n-1; i >= 0; i--){
            deliver += deliveries[i];
            pickup += pickups[i];
            
            while (deliver > 0 || pickup > 0){
                deliver -= cap;
                pickup -= cap;
                answer += (i+1) * 2;
            }

        }
        return answer;
    }
}

 

간단하게 풀이를 해보자면, 마찬가지로 가장 먼 집부터 처리를 해주는 건 똑같습니다.

1. 가장 먼 집부터 반복문을 돌려주고, 탐색된 집의 배송 수, 수거 수를 각각 '기록'해줍니다.
2. 그리고 기록된 배송 수, 수거 수가 0보다 크다면 반복문을 돌려주어 최대 허용량을 빼주고 이동 거리를 계산해 줍니다.

위 두 가지 방식으로 해결이 된다니 정말 놀라운 것 같습니다. 

저는 처음에는 1번까지는 이해가 되었지만, 2번은 이해하기 어려워 2번만 간단하게 설명해 보겠습니다.

 

1. 0 이하가 되기 전까지 반복하고, 반복될 때마다 탐색된 집 위치를 기준으로 이동거리를 계산해 주기

• 0 이하가 되기 전까지 계속 해당 집을 방문해야 하기 때문에 0 이하가 되기 전까지 cap 만큼 빼주고 이동거리를 계산해 주는 것입니다.

2. 그렇다면 왜 while의 조건문이 OR일까요?

• 이 부분도 마찬가지로 택배, 수거 둘 중 하나라도 처리해줘야 한다면 해당 집을 방문해야 하기 때문입니다.

3. cap을 빼다 보면 음수도 나오는데 음수는 왜 허용이 될까요?

• 사실, 이 부분이 제일 설명하기 어려운 것 같습니다...
• 음수가 되어도 괜찮은 이유는, 해당 코드는 가장 먼 집부터 처리한다고 하지만, 사실상 가장 먼 집을 처리하는데 cap이 남는 다면 가장 먼 집을 오기 전에 집의 배송 혹은 수거를 처리해 줄 수 있기 때문입니다.
• 즉, 음수가 된다는 건 가장 먼 집을 찾아오기 전에 다른 집을 처리해 줬다고 생각하면 좋을 것 같습니다.