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

문제

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

프로그래머스

---

풀이(30분)

class Solution {
    public long solution(int cap, int n, int[] deliveries, int[] pickups) {
        long answer = 0;
        int deliveryCheck = n - 1; // 배달을 해야 할 마지막 집의 인덱스
        int pickupCheck = n - 1;  // 수거를 해야 할 마지막 집의 인덱스

        while (deliveryCheck >= 0 || pickupCheck >= 0) { // 배달 또는 수거가 남아있는 동안 반복
            int nowCount = cap;
            int distance = 0;

            // **배달 작업**
            while (deliveryCheck >= 0 && deliveries[deliveryCheck] == 0) {
                deliveryCheck--; // 배달이 없는 집은 건너뛰기
            }
            if (deliveryCheck >= 0) {
                distance = deliveryCheck + 1; // 배달을 해야 할 가장 먼 집
            }

            while (deliveryCheck >= 0) {
                if (deliveries[deliveryCheck] > nowCount) { 
                    deliveries[deliveryCheck] -= nowCount; // 현재 용량만큼 배달
                    break; // 작업 중단
                } else {
                    nowCount -= deliveries[deliveryCheck]; // 용량 줄이기
                    deliveries[deliveryCheck] = 0; // 배달 완료
                    deliveryCheck--; // 다음 집으로 이동
                }
            }

            // **수거 작업**
            nowCount = cap; // 수거 작업을 위해 용량 초기화
            while (pickupCheck >= 0 && pickups[pickupCheck] == 0) {
                pickupCheck--; // 수거가 없는 집은 건너뛰기
            }
            if (pickupCheck >= 0) {
                distance = Math.max(distance, pickupCheck + 1); // 수거와 배달 중 더 먼 거리 계산
            }

            while (pickupCheck >= 0) {
                if (pickups[pickupCheck] > nowCount) {
                    pickups[pickupCheck] -= nowCount; // 현재 용량만큼 수거
                    break; // 작업 중단
                } else {
                    nowCount -= pickups[pickupCheck]; // 용량 줄이기
                    pickups[pickupCheck] = 0; // 수거 완료
                    pickupCheck--; // 다음 집으로 이동
                }
            }

            // **이동 거리 계산**
            answer += distance * 2; // 왕복 거리 계산
        }
        
        return answer; // 총 이동 거리 반환
    }
}

 

문제 자체에 대한 이해를 하는 것보다는 효율적인 알고리즘을 생각하는데 시간이 오래걸렸다.

결국 나온 생각은 그냥 끝에서부터 하나씩 해결해나가자는 것이었다.

 

1. 배송해야하는 집과, 수거해야하는 집이 모두 시작지점과 동일할때까지 반복한다.

2. 배송을 제일 멀리 가야하는 집을 먼저 distance에 담아두고 최대 물건을 내려줄 수 있는 것을 끝점부터 계산한다.

3. 픽업을 해야하는 제일 먼 집을 pickupCheck에 담아두고 최대 수거해올 수 있는 집을 끝점부터 계산한다.

4. 정답에 초기 distance에 담아둔 것과 pickupCheck에 담아둔 것 중 큰 것(즉 더 멀리 가야하는 이유가 있는 집)을 answer에 *2를 하여 더한다.(왕복거리이기 때문)

 

문제를 해결하고 보니 다른 분들은 스택을 사용하신 것 같은데, 실제로 스택을 사용해도 되지만 굳이 사용해야할 필요성을 느끼지 못하여 쓰지 않고 문제를 해결했다.