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

문제

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

프로그래머스

 

---

문제 설명

주어진 문제는 트럭의 배달 및 수거를 최소 이동 거리로 완료하는 방법을 찾는 것입니다. 트럭은 물류창고에서 출발하여 각 집을 순회하면서 택배를 배달하고 빈 택배 상자를 수거해야 합니다. 트럭의 최대 적재량은 cap으로 주어지며, deliveries와 pickups 배열이 각각 각 집에 배달할 택배 상자와 수거할 빈 택배 상자의 개수를 나타냅니다.

접근 방식

1. 뒤에서 앞으로 순회:
   • 마지막 집부터 첫 번째 집까지 역순으로 순회합니다. 이는 트럭이 이동하면서 가장 멀리 있는 집을 우선적으로 처리하기 위해서입니다.
2. 배달 및 수거 계산:
   • deliveries 배열을 순회하여 해당 집에 배달할 수 있는 택배 상자의 수를 처리하고 남은 수량을 조정합니다.
   • pickups 배열을 순회하여 해당 집에서 수거할 수 있는 빈 상자의 수를 처리하고 남은 수량을 조정합니다.
3. 필요 시 재방문:
   • 각 집에서 필요한 배달과 수거가 한 번에 완료되지 않으면 트럭은 물류창고로 돌아가야 하므로 왕복 거리를 누적합니다.
4. 이동 거리 계산:
   • 각 집에 방문할 때 필요한 왕복 거리를 누적합니다.

 

class Solution {
    public long solution(int cap, int n, int[] deliveries, int[] pickups) {
        long answer = 0;
        int d = 0;
        int p = 0;
        for(int i=n-1; i>=0; i--){
            d -= deliveries[i];
            p -= pickups[i];

            while(d < 0 || p < 0){
                d += cap;
                p += cap;
                answer += (i+1)*2;
            }
        }
        return answer;
    }
}