[Programmers] 택배 배달과 수거하기 (Java) - 2023 KAKAO BLIND RECRUITMENT

yeoni·2025년 2월 25일

ps 알고리즘

알고리즘 & 코딩 테스트

목록 보기

3/7

문제 링크

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

접근 방법

처음 문제를 읽어보면, 복잡하다고 생각할 수 있지만 예시와 상황을 찬찬히 살펴보면 그리디적으로 접근하면 쉽게 해결할 수 있다는 것을 금방 눈치챌 수 있다.

최소 거리로 이동하면서 모든 집에 배달 및 수거하기 위해서는, 가장 멀리 떨어진 집에 배달을 하면서 물류창고로 돌아올 때, 멀리 떨어진 집부터 택배 상자를 함께 수거해야 한다. 즉, 가장 거리가 먼 집부터 방문하고 돌아오면서 최대한 멀리 있는 집들의 택배 상자도 함께 수거하여 멀리 떨어진 집을 재방문 하지 않도록 하는 것이 핵심 이다.

구현

2개의 포인터를 두어, 각각의 포인터는 배달을 위한 가장 멀리 떨어진 집과 수거를 위한 가장 멀리 떨어진 집을 가르키도록 했다.

이때, deliveries 또는 pickups의 값이 0이라면, 굳이 방문하지 않아도 되는 집이므로 while문을 돌려 포인터를 이동시키는 작업을 사전에 추가해 주었다.

모든 물건을 배달 및 수거하고 다시 물류 창고로 돌아오는 왕복 거리이므로, 두 포인터 중 (더 멀리 떨어진 거리에 * 2)를 해주면 한 번 배달 및 수거하는데 이동한 거리가 된다.

이런식으로 2개의 포인터를 이동시켜가면서 최대 용량(CAP)만큼을 처리한 후, 다음에 배달 및 수거해야 할 집들 중 가장 멀리 떨어진 집의 인덱스를 포인터 값에 저장하는 식으로 구현하였다. 또한 배달을 모두 완료했더라도 상자를 수거해야할 집이 남아있다면(그 반대의 경우도 마찬가지) 다시 출발해야하므로 반복문을 수행할 조건은 2개 포인터 중 하나라도 0보다 클 경우로 설정하였다.

각 집을 한 번만 방문하면서 택배를 처리하기 때문에 시간 복잡도는 O(n)으로 문제에서 주어진 n의 범위가 1 ≤ n ≤ 100,000 이므로 시간 초과 또한 발생하지 않음을 알 수 있다.

최종 코드

class Solution {
    public long solution(int cap, int n, int[] deliveries, int[] pickups) {
        long distance = 0L;
        int end1 = n - 1, end2 = n - 1;

        // 배달과 수거의 끝 지점 찾기
        while (end1 >= 0 && deliveries[end1] == 0) {
            end1--;
        }
        while (end2 >= 0 && pickups[end2] == 0) {
            end2--;
        }

        while (end1 >= 0 || end2 >= 0) {
            // 가장 먼 곳까지 가야 함 (왕복이므로 *2를 해줌)
            distance += (Math.max(end1, end2) + 1) * 2;

            // 배달 물량 처리
            int give = cap;
            while (give >= 0 && end1 >= 0) {
                give -= deliveries[end1];
                if (give < 0) {
                    deliveries[end1] = give * -1;
                    break;
                } else {
                    end1--;
                }
            }

            // 수거 물량 처리
            int get = cap;
            while (get >= 0 && end2 >= 0) {
                get -= pickups[end2];
                if (get < 0) {
                    pickups[end2] = get * -1;
                    break;
                } else {
                    end2--;
                }
            }
        }

        return distance;
    }
}

최종 코드는 위와 같다.