Lv 2. 택배 배달과 수거하기

 

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

프로그래머스

 

 

 

📌 자바(Java)로 푸는 

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

 🚚📦

 

---

🔎 문제 개요

 

프로그래머스 Lv.2 - 택배 배달과 수거하기 문제입니다.

트럭이 정해진 용량(cap)만큼 배달/수거를 하며 모든 집에 물건을 배달하고 수거하려고 합니다.

왕복 이동 거리의 최솟값을 구하는 것이 목표입니다.

 

---

💡 예제 입력

cap = 4, n = 5
deliveries = [1, 0, 3, 1, 2]
pickups = [0, 3, 0, 4, 0]

 

💡 예제 출력

16

➡ 물건을 배달하고 수거하기 위해 왕복한 거리의 총합이 16

 

---

🛠 알고리즘 접근 방식

 

이 문제는 거꾸로(가장 먼 집부터) 순회하면서, cap 만큼 배달/수거를 처리하며 왕복 횟수를 누적하는 방식으로 해결할 수 있습니다.

 

 

✏️ 핵심 아이디어

 

• 먼 집부터 처리하면 한 번 갈 때 최대한 많은 배달/수거를 묶을 수 있음
• 배달과 수거는 동시에 가능하므로 두 작업을 같이 관리
• deliver, pickup은 **남은 잔여 작업량(미처리된 수량)**을 의미

 

---

🔹 Java 코드 해설

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. 뒤에서부터 순회하는 이유

for(int i = n - 1; i >= 0; i--)

✔ 먼 거리부터 먼저 배달/수거 → 왕복 횟수 최소화

✔ 이후 집은 같은 이동으로 묶어서 처리 가능

 

---

📌 2. 잔여 작업량 계산

deliver -= deliveries[i];
pickup -= pickups[i];

✔ 현재 집에서 배달할 양과 수거할 양을 각각 차감

✔ 남은 양이 0보다 작다는 건 아직 더 가져가야 한다는 의미

 

---

📌 3. 필요한 만큼 트럭 보내기

while (deliver < 0 || pickup < 0) {
    deliver += cap;
    pickup += cap;
    answer += (i + 1) * 2;
}

✔ 남은 배달/수거량이 존재할 때마다 트럭 한 번 더 왕복

✔ cap만큼만 처리 가능하므로 누적하면서 반복 수행

 

---

🏆 정리

 

 

✅ 핵심 포인트

 

✔ 먼 곳부터 처리 → 왕복 거리 최소화

✔ 한 번 갈 때 배달/수거를 함께 처리하여 최적의 거리 확보

✔ 그리디 방식 + 누적 처리

 

---

🎯 이 알고리즘의 장점

 

✅ 복잡한 조건 없이도 간단한 반복문으로 해결 가능

✅ 트럭의 적재량(cap)을 잘 활용하여 최적화 가능

✅ 현실적인 배달/수거 로직을 반영한 좋은 시뮬레이션 문제

---

 

필요하면 이 문제에 대한 블로그 글 형태로도 정리해드릴게요! 😊