[프로그래머스] 2023 KAKAO BLIND - 택배 배달과 수거하기 (자바)

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

프로그래머스

---

문제 

택배 배달을 해야하는 deliveries 배열과 픽업 배열인 pickups 가 주어졌을 때

배달과 픽업을 모두 마칠 수 있는 최단 거리를 구하는 문제 

 

여기서 최단 거리는 결국 가장 멀리있는 배달 or 픽업을 먼저 해서 이동거리를 최소한으로 줄이면 된다. 

그리디로 쉽게 접근할 수 있고 생각보다 시간초과에 걸리는 문제가 몇 있어 반복문 중에서 break 조건을 잘 걸어주어야 한다. 

 

---

풀이

 

어차피 배달은 최대 적재 수량만큼 채워서 나갈 것이고, 

특정 집 까지 배달을 마치면 돌아올 때 픽업 수량도 최대 적재 수량만큼 다시 채워서 올 수 있다는 점을 고려하면

 

배달과 픽업을 각각 생각하는 것이 풀이에 도움이 되었다. 

배달과 픽업을 각각 나갔을 때, 둘 중 더 먼 거리를 answer 에 더해주면 답이 된다. 

 

 

루프 탈출 조건은 

처음 시작 전에 각 배달 총량, 픽업 총량을 계산하여 이 두가지의 총량이 0이 될 때 반복문을 탈출하도록 했다. 

 

import java.util.Arrays;

class Solution {
    public long solution(int cap, int n, int[] deliveries, int[] pickups) {
        long answer = 0;
        int dstart = n - 1;
        int pstart = n - 1;
    
        int dtotal = Arrays.stream(deliveries).sum();
        int ptotal = Arrays.stream(pickups).sum();
        
        while(true) {
            int dcap = cap;
            int pcap = cap;
            int index = -1;
            
            // delivery
            for(int i = dstart; i >= 0; i--) {
                if (deliveries[i] > 0) {
                    index = Math.max(index, i);
    
                    if (deliveries[i] <= dcap) {
                        dcap -= deliveries[i];
                        dtotal -= deliveries[i];
                        deliveries[i] = 0;
                    } else {
                        deliveries[i] -= dcap;
                        dstart = i;
                        dtotal -= dcap;
                        break;
                    }
                }
            }
            
            // pickup
            for(int i = pstart; i >= 0; i--) {
                if (pickups[i] > 0) {
                    index = Math.max(index, i);
    
                    if (pickups[i] <= pcap) {
                        pcap -= pickups[i];
                        ptotal -= pickups[i];
                        pickups[i] = 0;
                    } else {
                        pickups[i] -= pcap;
                        pstart = i;
                        ptotal -= pcap;
                        break;
                    }
                }
            }
            
            if (index >= 0) {
                answer += (index + 1) * 2;
            }
            if (dtotal == 0 && ptotal == 0) {
                break;
            }
            
        }
        
        
        return answer;
    }
}