프로그래머스 | Level 2 | 택배 배달과 수거하기

Programmers | Level 2 | 택배 배달과 수거하기

Problems

• 📘 Src: Programmers
• 🗂️ Cat: Greedy

󰧭 Description

당신은 일렬로 나열된 n개의 집에 택배를 배달하려 합니다. 배달할 물건은 모두 크기가 같은 재활용 택배 상자에 담아 배달하며, 배달을 다니면서 빈 재활용 택배 상자들을 수거하려 합니다.

배달할 택배들은 모두 재활용 택배 상자에 담겨서 물류창고에 보관되어 있고, i번째 집은 물류창고에서 거리 i만큼 떨어져 있습니다. 또한 i번째 집은 j번째 집과 거리 j - i만큼 떨어져 있습니다. (1 ≤ i ≤ j ≤ n)

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

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

배달 및 수거할 재활용 택배 상자 개수

	집 #1	집 #2	집 #3	집 #4	집 #5
배달	1개	0개	3개	1개	2개
수거	0개	3개	0개	4개	0개

배달 및 수거 과정

	집 #1	집 #2	집 #3	집 #4	집 #5	설명
남은 배달/수거	1/0	0/3	3/0	1/4	2/0	물류창고에서 택배 3개를 트럭에 실어 출발합니다.
남은 배달/수거	1/0	0/3	3/0	0/4	0/0	물류창고에서 5번째 집까지 이동하면서(거리 5), 4번째 집에 택배 1개를 배달하고, 5번째 집에 택배 2개를 배달합니다.
남은 배달/수거	1/0	0/3	3/0	0/0	0/0	5번째 집에서 물류창고까지 이동하면서(거리 5), 4번째 집에서 빈 택배 상자 4개를 수거한 후, 수거한 빈 택배 상자를 물류창고에 내리고 택배 4개를 트럭에 싣습니다.
남은 배달/수거	0/0	0/3	0/0	0/0	0/0	물류창고에서 3번째 집까지 이동하면서(거리 3), 1번째 집에 택배 1개를 배달하고, 3번째 집에 택배 3개를 배달합니다.
남은 배달/수거	0/0	0/0	0/0	0/0	0/0	3번째 집에서 물류창고까지 이동하면서(거리 3), 2번째 집에서 빈 택배 상자 3개를 수거한 후, 수거한 빈 택배 상자를 물류창고에 내립니다.

16(=5+5+3+3)의 거리를 이동하면서 모든 배달 및 수거를 마쳤습니다. 같은 거리로 모든 배달 및 수거를 마치는 다른 방법이 있지만, 이보다 짧은 거리로 모든 배달 및 수거를 마치는 방법은 없습니다.

트럭에 실을 수 있는 재활용 택배 상자의 최대 개수를 나타내는 정수 cap, 배달할 집의 개수를 나타내는 정수 n, 각 집에 배달할 재활용 택배 상자의 개수를 담은 1차원 정수 배열 deliveries와 각 집에서 수거할 빈 재활용 택배 상자의 개수를 담은 1차원 정수 배열 pickups가 매개변수로 주어집니다. 이때, 트럭 하나로 모든 배달과 수거를 마치고 물류창고까지 돌아올 수 있는 최소 이동 거리를 return 하도록 solution 함수를 완성해 주세요.

 Constraints

• 1 ≤ cap ≤ 50
• 1 ≤ n ≤ 100,000
• deliveries의 길이 = pickups의 길이 = n
  • deliveries[i]는 i + 1번째 집에 배달할 재활용 택배 상자의 개수를 나타냅니다.
  • pickups[i]는 i + 1번째 집에서 수거할 빈 재활용 택배 상자의 개수를 나타냅니다.
  • 0 ≤ deliveries의 원소 ≤ 50
  • 0 ≤ pickups의 원소 ≤ 50
• 트럭의 초기 위치는 물류창고입니다.

󰦕 Examples

cap	n	deliveries	pickups	result
4	5	[1, 0, 3, 1, 2]	[0, 3, 0, 4, 0]	16
2	7	[1, 0, 2, 0, 1, 0, 2]	[0, 2, 0, 1, 0, 2, 0]	30

Solutions

󰘦 Code

import java.util.*;

class Solution {
    public long solution(int cap, int n, int[] deliveries, int[] pickups) {
        long totalDist = 0;  // 최소 이동 거리
        int dIdx = n - 1;    // 배달 작업 시작 위치
        int pIdx = n - 1;    // 수거 작업 시작 위치
        
        // 작업할 총 상자 수 계산
        int tasks = 0;
        for (int i = 0; i < n; i++) {
            tasks += deliveries[i];
            tasks += pickups[i];
        }
        
        // 모든 작업이 끝날 때까지 반복
        while (tasks > 0) {
            int singleDist = Math.max(dIdx, pIdx) + 1;  // 현재 왕복 거리 계산
            totalDist += singleDist * 2;  // 왕복 거리 누적
            
            int currCap = cap;  // 배달 용량 초기화
            // 배달 작업
            while (dIdx >= 0 && currCap > 0) {
                if (deliveries[dIdx] <= currCap) {
                    currCap -= deliveries[dIdx];
                    tasks -= deliveries[dIdx];
                    deliveries[dIdx] = 0;
                    dIdx--;
                } else {
                    deliveries[dIdx] -= currCap;
                    tasks -= currCap;
                    currCap = 0;
                }
            }
            
            currCap = cap;  // 수거 용량 초기화
            // 수거 작업
            while (pIdx >= 0 && currCap > 0) {
                if (pickups[pIdx] <= currCap) {
                    currCap -= pickups[pIdx];
                    tasks -= pickups[pIdx];
                    pickups[pIdx] = 0;
                    pIdx--;
                } else {
                    pickups[pIdx] -= currCap;
                    tasks -= currCap;
                    currCap = 0;
                }
            }
            
            // 배달 및 수거가 완료된 위치 갱신
            while (dIdx >= 0 && deliveries[dIdx] == 0) {
                dIdx--;
            }
            while (pIdx >= 0 && pickups[pIdx] == 0) {
                pIdx--;
            }
        }
        
        return totalDist;  // 최소 이동 거리 반환
    }
}

 Approaches

이 문제는 양방향으로 동시에 배달과 수거를 진행해야 하는 탐욕적 접근법(Greedy Algorithm) 문제입니다. 왕복 거리를 최소화하기 위해 배달과 수거를 효율적으로 배분하며 각 집에 도달하도록 설계합니다.

1. 문제 분석

이 문제는 여러 집에 택배 상자를 배달하고, 수거할 상자를 회수하여 물류창고로 돌아오는 과정에서 최소 거리를 구하는 최적화 문제입니다. 각 집의 위치에 따른 거리와 트럭의 적재 용량 제한을 고려하면서, 배달과 수거 작업을 동시에 처리하여 이동 거리를 줄이는 것이 핵심입니다.

효율적인 해결을 위해, 가장 멀리 있는 집부터 시작해 배달과 수거를 한 번에 최대한 수행하는 방식이 필요합니다. 이러한 방식은 끝에서부터 작업을 진행하며, 배달과 수거 중 작업량이 큰 쪽을 기준으로 트럭을 가득 채우고 이동하는 탐욕적 접근으로 구현할 수 있습니다. 이로써 멀리 있는 집에 갈 때마다 최대 작업량을 수행하게 되어 불필요한 왕복을 줄일 수 있습니다.

문제를 해결하는 핵심 요소는 매번 트럭이 최대한의 배달과 수거를 수행하도록 하고, 이를 위해 배달과 수거 중 어느 쪽이 더 많은 작업을 요구하는지 파악해 트럭의 용량을 최대로 활용하는 것입니다. 각 왕복에서 수행할 작업이 많아질수록 전체 이동 거리의 최적화가 가능해집니다.

2. 접근 방식

문제를 효율적으로 해결하기 위해 각 배열의 끝에서부터 탐색하며, 매 왕복에서 최대한 많은 작업을 수행합니다. 구체적인 과정은 다음과 같습니다:

1. 작업량 초기화 및 확인: 각 배열에 남은 배달 또는 수거 작업량이 없는 경우에는 추가 탐색이나 이동이 필요하지 않으므로, 이를 고려해 초기 작업량을 설정합니다.
2. 왕복 거리 계산: 배달과 수거 중 가장 멀리 떨어진 집까지의 거리를 계산하고, 해당 거리를 왕복 거리로 누적합니다. 이 방식은 멀리 떨어진 집부터 배달 및 수거 작업을 우선 처리하여 이동 거리를 최소화할 수 있도록 합니다.
3. 배달 작업 수행: 트럭의 최대 용량(cap)을 기준으로, 현재 왕복에서 가능한 최대한의 배달 상자를 싣고 배달합니다. 남아 있는 배달 상자가 있으면 계속해서 작업을 진행하며, 각 집의 배달 작업이 끝난 후에는 다음 집으로 이동하여 작업을 이어갑니다.
4. 수거 작업 수행: 배달과 동일하게 수거 작업도 용량 제한을 고려하여 최대한의 상자를 회수합니다. 수거할 상자가 남아 있을 경우에는 가능한 최대한으로 작업을 이어가며, 각 집에서의 수거 작업이 끝나면 다음 집으로 이동합니다.
5. 위치 업데이트: 현재 왕복에서 배달과 수거 작업이 모두 완료되면, 아직 작업이 남아 있는 집 중 가장 먼 집을 새로운 목표 지점으로 설정하여 효율적인 반복이 이루어지도록 합니다.

3. 작업 초기화 및 시작점 설정

각 집에서 배달 및 수거해야 할 상자의 수를 모두 합산하여 총 작업량을 계산합니다. 이 값이 0이 되면 모든 작업이 완료된 것으로 간주하며, 이를 반복문에서 종료 조건으로 활용합니다. 작업은 각 배열의 끝, 즉 가장 먼 집부터 시작하는데, 이는 최대한 많은 작업을 왕복할 때 멀리 떨어진 집부터 먼저 처리하여 불필요한 이동 거리를 줄이기 위함입니다. 멀리 떨어진 집을 목표로 삼아 배달과 수거 작업을 한 번의 왕복으로 처리하는 방식은 이동 거리를 최소화하는 데 유리합니다.

int dIdx = n - 1;  // 배달 작업의 시작 위치 (배열 끝)
int pIdx = n - 1;  // 수거 작업의 시작 위치 (배열 끝)

// 전체 작업량 계산: 배달 및 수거 상자 수의 합
int tasks = 0;
for (int i = 0; i < n; i++) {
    tasks += deliveries[i];
    tasks += pickups[i];
}

4. 배달 작업 수행 및 왕복 거리 누적

모든 작업이 완료될 때까지 각 위치에서 필요한 왕복 거리를 계산하며, 트럭의 용량을 고려해 최대한 많은 상자를 배달 및 수거합니다.

• 왕복 거리 계산: 현재 배달할 위치(dIdx)와 수거할 위치(pIdx) 중 더 멀리 있는 위치를 기준으로 왕복 거리를 계산하여 누적합니다. 이렇게 멀리 있는 집부터 작업을 처리하면 이동 거리를 최소화할 수 있습니다.
• 배달 작업 수행: 현재 위치부터 시작해 트럭에 남은 용량 내에서 최대한 많은 상자를 배달합니다. 현재 위치의 상자 배달이 완료되면 다음 집으로 이동하여 반복하며, 작업이 완료되면 위치를 갱신합니다.
• 수거 작업 수행: 수거도 동일하게 진행하여 트럭 용량이 허용하는 최대 수량을 회수합니다. 현재 위치의 상자를 모두 수거하면 다음 집으로 이동하며, 작업 완료 시 위치를 갱신합니다.
• 남은 작업이 있는 집으로 위치 갱신: 현재 왕복이 끝나면 남은 작업이 있는 가장 멀리 있는 집을 새로운 목표 위치로 설정하여 다음 왕복을 준비합니다.

long totalDist = 0;
while (tasks > 0) {
    int singleDist = Math.max(dIdx, pIdx) + 1;  // 현재 왕복 거리 계산
    totalDist += singleDist * 2;  // 왕복 거리 누적
    
    int currCap = cap;  // 트럭의 남은 배달 용량
    // 배달 작업 수행
    while (dIdx >= 0 && currCap > 0) {
        if (deliveries[dIdx] <= currCap) {  // 현재 위치의 배달량이 남은 용량 이내인 경우
            currCap -= deliveries[dIdx];  // 트럭에 배달 상자 추가
            tasks -= deliveries[dIdx];  // 전체 작업량에서 배달 상자 차감
            deliveries[dIdx] = 0;  // 해당 집의 배달 완료
            dIdx--;  // 다음 집으로 이동
        } else {
            deliveries[dIdx] -= currCap;  // 남은 용량만큼 배달
            tasks -= currCap;
            currCap = 0;  // 트럭 용량이 가득 찬 경우
        }
    }
    
    currCap = cap;  // 트럭의 남은 수거 용량
    // 수거 작업 수행
    while (pIdx >= 0 && currCap > 0) {
        if (pickups[pIdx] <= currCap) {  // 현재 위치의 수거량이 남은 용량 이내인 경우
            currCap -= pickups[pIdx];  // 트럭에 수거 상자 추가
            tasks -= pickups[pIdx];  // 전체 작업량에서 수거 상자 차감
            pickups[pIdx] = 0;  // 해당 집의 수거 완료
            pIdx--;  // 다음 집으로 이동
        } else {
            pickups[pIdx] -= currCap;  // 남은 용량만큼 수거
            tasks -= currCap;
            currCap = 0;  // 트럭 용량이 가득 찬 경우
        }
    }
    
    // 남은 작업이 있는 집 탐색하여 위치 갱신
    while (dIdx >= 0 && deliveries[dIdx] == 0) {
        dIdx--;  // 남은 배달 작업이 있는 가장 먼 집을 찾음
    }
    while (pIdx >= 0 && pickups[pIdx] == 0) {
        pIdx--;  // 남은 수거 작업이 있는 가장 먼 집을 찾음
    }
}

5. 결과 반환

모든 배달 및 수거 작업이 완료되면 누적된 이동 거리를 반환합니다. 이 값은 최소한의 왕복 거리로 배달과 수거를 완료한 최종 이동 거리입니다.

// 모든 배달 및 수거 작업이 완료되면 총 이동 거리 반환
return totalDist;

󰄉 Complexity

• ⏳ TC: O(N)
• 💾 SC: O(1)

각 집에서 배달 및 수거 작업을 한 번씩 수행하며, 루프를 통해 각 집을 최대 한 번씩 방문합니다. 따라서 시간 복잡도는 O(N)입니다. 필요한 변수는 거리와 현재 작업 위치를 추적하기 위한 변수들뿐이므로, 추가적인 배열을 사용하지 않는 점에서 공간 복잡도는 O(1)입니다.