[programmers/java] 택배 배달과 수거하기

문제 요약

• https://school.programmers.co.kr/learn/courses/30/lessons/150369?language=java
• 택배 기사가 집마다 배달할 박스와 수거할 박스를 가지고 있음
• 한 번에 운반 가능한 박스 수는 cap개
• 왕복 이동 시 가장 멀리 가는 위치 기준으로 거리 누적
• 목적: 모든 배달과 수거를 완료하는 최소 이동 거리 계산

---

접근 전략

이 문제는 단순히 배열을 순회하며 처리하는 방식으로는 거리 최적화를 구현하기 어렵다. 가장 중요한 포인트는 다음과 같다:

❗ 한 번의 이동으로 배달과 수거를 동시에 처리하고, 이동 거리 기준은 가장 멀리 가는 위치여야 한다.

이를 위해 다음과 같은 방법으로 접근한다.

1. 우선순위 큐(PriorityQueue)를 사용해 먼 위치부터 처리

• idx가 큰 집부터 처리하면 이동 거리를 줄일 수 있음
• Java에서는 PriorityQueue를 사용하여 위치 기준 최대 힙 구성

2. (위치, 수량) 형태로 데이터를 묶어 한 번에 관리

• 박스 수만큼 큐에 idx를 여러 번 넣는 방식은 비효율적
• → (idx, count) 형태의 Node 클래스를 사용하여 위치별 박스 수를 한번에 처리

3. cap만큼 처리 후 남은 양은 다시 큐에 삽입

• 하나의 이동에서 최대 cap만큼 배달/수거 처리
• 남은 수량은 다시 큐에 삽입해 다음 루프에서 이어서 처리

---

Code

import java.util.*;

class Solution {
    public long solution(int cap, int n, int[] deliveries, int[] pickups) {
        // 배달/수거 우선순위 큐: idx 큰 순서(=가장 먼 집부터) 처리
        PriorityQueue<Node> deliveriesQ = new PriorityQueue<>((a, b) -> b.idx - a.idx);
        PriorityQueue<Node> pickupsQ = new PriorityQueue<>((a, b) -> b.idx - a.idx);

        // 배열 데이터를 큐에 옮김: 위치(idx), 박스 수(count)
        for (int i = 0; i < n; i++) {
            if (deliveries[i] > 0) deliveriesQ.offer(new Node(i + 1, deliveries[i]));
            if (pickups[i] > 0) pickupsQ.offer(new Node(i + 1, pickups[i]));
        }

        long answer = 0;

        // 둘 중 하나라도 남아 있으면 계속 반복
        while (!deliveriesQ.isEmpty() || !pickupsQ.isEmpty()) {
            int dist = 0;         // 이번 루프에서 이동해야 할 가장 먼 위치
            int remainD = cap;    // 남은 배달 용량
            int remainP = cap;    // 남은 수거 용량

            // 배달 처리
            while (!deliveriesQ.isEmpty() && remainD > 0) {
                Node node = deliveriesQ.poll();
                dist = Math.max(dist, node.idx); // 가장 먼 위치 갱신

                // 이번 이동으로 모두 배달 가능
                if (node.count <= remainD) {
                    remainD -= node.count;
                }
                // 일부만 배달 가능 → 나머지는 다음에 다시 처리
                else {
                    deliveriesQ.offer(new Node(node.idx, node.count - remainD));
                    remainD = 0;
                }
            }

            // 수거 처리 (배달과 동일 로직)
            while (!pickupsQ.isEmpty() && remainP > 0) {
                Node node = pickupsQ.poll();
                dist = Math.max(dist, node.idx); // 가장 먼 위치 갱신

                if (node.count <= remainP) {
                    remainP -= node.count;
                } else {
                    pickupsQ.offer(new Node(node.idx, node.count - remainP));
                    remainP = 0;
                }
            }

            // 가장 먼 위치까지 왕복 거리 누적
            answer += dist * 2L;
        }

        return answer;
    }

    // 위치와 박스 수를 저장할 Node 클래스
    class Node {
        int idx;    // 집의 위치
        int count;  // 배달/수거해야 할 박스 수

        public Node(int idx, int count) {
            this.idx = idx;
            this.count = count;
        }
    }
}