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

 

문제

 

당신은 일렬로 나열된 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. 배달 양이 넘치는 경우에는 공간(배달/수거) 남는 경우가 발생할 수 있다.

처음에는 누적합을 역순으로 구해서 풀어볼 생각을 했지만 0에 대한 처리가 까다로워 그냥 그리디 알고리즘으로 풀이를 시도 했다. 

 

import java.util.*;

class Solution {
    public long solution(int cap, int n, int[] deliveries, int[] pickups) {
        long answer = 0;
        int d = 0, p = 0;  // 현재 트럭에 실린 배달과 수거 상자 수
    
        for (int i = n - 1; i >= 0; i--) {
            int roundTrips = 0; 
            
            // 최대한 수거할 수 있는 횟수 구하기 
            while (d < deliveries[i] || p < pickups[i]) {
                roundTrips++;
                d += cap;
                p += cap;
            }
            
            answer += (i + 1) * roundTrips * 2;
            
            d -= deliveries[i];
            p -= pickups[i];
        }
        
        return answer;
    }
}