[JAVA] 알고리즘 스터디 4주차 공통과제: KAKAO 택배 배달과 수거하기 📦 | 배열 풀이

 

[JAVA] 알고리즘 스터디 4주차 공통과제: KAKAO 택배 배달과 수거하기 

프로그래머스

 

🔒 문제

당신은 일렬로 나열된 n개의 집에 택배를 배달하려 합니다. 배달할 물건은 모두 크기가 같은 재활용 택배 상자에 담아 배달하며, 배달을 다니면서 빈 재활용 택배 상자들을 수거하려 합니다.
배달할 택배들은 모두 재활용 택배 상자에 담겨서 물류창고에 보관되어 있고, i번째 집은 물류창고에서 거리 i만큼 떨어져 있습니다. 또한 i번째 집은 j번째 집과 거리 j - i만큼 떨어져 있습니다. (1 ≤ i ≤ j ≤ n)
트럭에는 재활용 택배 상자를 최대 cap개 실을 수 있습니다. 트럭은 배달할 재활용 택배 상자들을 실어 물류창고에서 출발해 각 집에 배달하면서, 빈 재활용 택배 상자들을 수거해 물류창고에 내립니다. 각 집마다 배달할 재활용 택배 상자의 개수와 수거할 빈 재활용 택배 상자의 개수를 알고 있을 때, 트럭 하나로 모든 배달과 수거를 마치고 물류창고까지 돌아올 수 있는 최소 이동 거리를 구하려 합니다. 각 집에 배달 및 수거할 때, 원하는 개수만큼 택배를 배달 및 수거할 수 있습니다.

 

트럭에 실을 수 있는 재활용 택배 상자의 최대 개수를 나타내는 정수 cap, 배달할 집의 개수를 나타내는 정수 n, 각 집에 배달할 재활용 택배 상자의 개수를 담은 1차원 정수 배열 deliveries와 각 집에서 수거할 빈 재활용 택배 상자의 개수를 담은 1차원 정수 배열 pickups가 매개변수로 주어집니다. 이때, 트럭 하나로 모든 배달과 수거를 마치고 물류창고까지 돌아올 수 있는 최소 이동 거리를 return 하도록 solution 함수를 완성해 주세요.

 

---

🔎  풀이

진짜 말도 안 되게 삽질을 많이 한 문제이다. 처음엔 배열 자체를 사용하는 방법으로 풀이를 하다가 계속 오답이 나길래 다른 사람들 풀이를 참고했더니 스택이나 덱을 사용하는 사람들이 많았다. 그래서 손민수 해서 그렇게 구현하려고 했지만 내가 직접 생각해 낸 풀이가 아니니까 계속 막히고 이해가지 않는 부분이 많아 풀이가 어려웠다. 그래서 처음에 구현했던 대로 배열을 사용해서 구현을 했는데 반복문에 조건을 바꿔주니 해결이 됐다!

 

원리는 다음과 같다. 기사가 최소로 이동하려면 한 번 나갈 때 택배 상자를 'cap만큼 가지고', '가장 먼 곳에 주문이 있는 집'을 향해 가는데 이때 가는 길에 택배 전송을 해결하고, 돌아오는 길에 'cap만큼 회수'해 온다.

 

이 원리는 사용해서 구현하면 된다. 특히 전체 for문의 조건을 설정하는 것이 어려웠다. 항상 for문의 구성 요소인 시작점, 종료 조건, 갱신을 모두 채워서 구현했었는데 이번에는 특별한 조건에 의해서만 갱신이 일어나야 하므로 갱신 조건을 비워둬야 했다.

그리고 i가 n-1(가장 끝 인덱스)부터 시작해서 0이 될 때까지 순회한다.

이때 포인트는 i 갱신 조건을 for문 안에서 지정하지 않았으니까 현재 i인덱스 값이 0보다 작을 때까지 계속해서 반복문을 실행한다.

이유는 당연하다. deliveries[i]나 pickups[i] 값이 cap보다 클 경우 기사는 i의 주문이 소진될 때까지 반복해서 i로 와야 하니까.

 

배달이나 수거 주문이 있는 집을 발견했다면 distance에 해당 i의 왕복 거리를 더하고, 배달과 수거를 진행한다.

for문을 사용해 i부터 하나씩 줄어들면서 가정집에 방문에 택배를 배달 혹은 수거한다. 이때 최대 상자 수용 개수인 cap이 채워지면 break 하고, 그렇지 않으면 배열값을 빼준다. 배열값을 갱신했다는 것은 그만큼 택배를 수거 혹은 배달했다는 얘기다. 

 

🔹 전체 풀이 

import java.util.Arrays;

class Solution {
    public long solution(int cap, int n, int[] deliveries, int[] pickups) {

        long distance = 0;

        for( int i = n-1 ; i > -1; ){ // 택배 배달
            if( deliveries[i] <= 0 && pickups[i] <= 0 ) { // 아무 특이사항 없으면 패스
                i--;
                continue;
            }
			
            // 배달 및 수거할 물건이 있는 가장 멀리 있는 집 i
            distance += ( 2L * ( i + 1 ) );

            // [1] 배달하기
            int deliveryCap = cap;
            for( int j = i; j > -1; j-- ){ // cap만큼 채워서 배달하기
                if( deliveryCap <= 0) break;
                if( deliveries[j] > 0 ){
                    int tmp = deliveryCap;
                    deliveryCap -= deliveries[j];
                    deliveries[j] -= tmp;
                }
            }

            // [2] 픽업하기
            int pickupCap = cap;
            for( int j = i; j > -1; j-- ){ // cap만큼 채워서 회수해오기
                if(pickupCap<=0) break;
                if( pickups[j] > 0  ){
                    int tmp = pickupCap;
                    pickupCap -= pickups[j];
                    pickups[j] -= tmp;
                }
            }
        }

        return distance;
    }

}

 

 ⌛️ 복잡도 계산

- 시간 복잡도 :  O(N^2)

0부터 n-1까지 순회하는 큰 for문 내부에 최악의 경우 0부터 n-1까지 순회하는 for문이 두 개 있으므로 시간 복잡도는  O(N^2)

 

- 공간 복잡도: O(N)

크기가 n인 주어진 배열 두 개를 그대로 활용하므로 공간 복잡도는 O(N)