택배 배달과 수거하기

문제

프로그래머스 - 택배 배달과 수거하기

---

문제 해결 아이디어

이 문제는 뒤쪽(가장 먼 집)부터 처리하는 그리디 알고리즘을 활용해야겠다고 생각했다!

1. 뒤쪽부터 처리하기

   • 집들은 물류창고에서 가까운 순서대로 1번부터 n번까지 배치되어 있으므로, 가장 먼 집부터 남은 배달 또는 수거가 있는 집까지의 거리를 기준으로 처리

2. 최대 거리 결정

   • 아직 처리할 배달이나 수거가 남은 집들 중 가장 먼 집의 번호를 찾기
   • 해당 집까지의 왕복 거리는 (집 번호 = index + 1) * 2

3. 한 번 이동에서 cap 만큼 처리

   • 트럭의 용량 cap만큼 배달과 수거 작업을 진행
   • 각각의 배열에서 가장 먼 집부터 cap 만큼의 택배 상자를 처리하고, 남은 건수 갱신

4. 반복 처리

   • 모든 집에 대한 배달 및 수거가 완료될 때까지 위 과정을 반복하며, 이동 거리 누적

---

코드

import java.util.*;

class Solution {
    public long solution(int cap, int n, int[] deliveries, int[] pickups) {
        long answer = 0;
        int dIdx = n - 1; // deliveries의 마지막 인덱스 (가장 먼 집)
        int pIdx = n - 1; // pickups의 마지막 인덱스 (가장 먼 집)
        
        // 아직 배달 또는 수거할 집이 남아있는 동안 반복
        while (dIdx >= 0 || pIdx >= 0) {
            // 배달할 집 중 남은 건수가 0인 집은 건너뛰기
            while (dIdx >= 0 && deliveries[dIdx] == 0) {
                dIdx--;
            }
            // 수거할 집 중 남은 건수가 0인 집은 건너뛰기
            while (pIdx >= 0 && pickups[pIdx] == 0) {
                pIdx--;
            }
            
            // 배달과 수거가 모두 완료되었다면 종료
            if (dIdx < 0 && pIdx < 0) {
                break;
            }
            
            // 이번 회 이동할 최대 거리는 두 포인터 중 더 큰 값(인덱스)에 1을 더한 거리
            int dist = Math.max(dIdx, pIdx) + 1;
            answer += (long) dist * 2;  // 왕복 이동 거리 누적
            
            int deliverCap = cap; // 이번 회 배달 처리에 사용할 남은 용량
            int pickupCap = cap;  // 이번 회 수거 처리에 사용할 남은 용량
            
            // 배달 처리: 가장 먼 집부터 cap 만큼 배달을 처리
            while (dIdx >= 0 && deliverCap > 0) {
                if (deliveries[dIdx] <= deliverCap) {
                    deliverCap -= deliveries[dIdx];
                    deliveries[dIdx] = 0;
                    dIdx--;
                } else {
                    deliveries[dIdx] -= deliverCap;
                    deliverCap = 0;
                }
            }
            
            // 수거 처리: 가장 먼 집부터 cap 만큼 수거를 처리
            while (pIdx >= 0 && pickupCap > 0) {
                if (pickups[pIdx] <= pickupCap) {
                    pickupCap -= pickups[pIdx];
                    pickups[pIdx] = 0;
                    pIdx--;
                } else {
                    pickups[pIdx] -= pickupCap;
                    pickupCap = 0;
                }
            }
        }
        
        return answer;
    }
}