[프로그래머스 Level.2] 택배 배달과 수거하기 (2023 KAKAO BLIND RECRUITMENT) (Java)

문제 링크

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

프로그래머스

 

 

 

코딩테스트 연습 > 2023 KAKAO BLIND RECRUITMENT > 택배 배달과 수거하기

 

 

문제 설명

 

 

 

 

당신은 일렬로 나열된 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	집 #4	집 #5	설명
남은 배달/수거	1/0	0/3	3/0	1/4	2/0	물류창고에서 택배 3개를 트럭에 실어 출발합니다.
남은 배달/수거	1/0	0/3	3/0	0/4	0/0	물류창고에서 5번째 집까지 이동하면서(거리 5) 4번째 집에 택배 1개를 배달하고, 5번째 집에 택배 2개를 배달합니다.
남은 배달/수거	1/0	0/3	3/0	0/0	0/0	5번째 집에서 물류창고까지 이동하면서(거리 5) 4번째 집에서 빈 택배 상자 4개를 수거한 후, 수거한 빈 택배 상자를 물류창고에 내리고 택배 4개를 트럭에 싣습니다.
남은 배달/수거	0/0	0/3	0/0	0/0	0/0	물류창고에서 3번째 집까지 이동하면서(거리 3) 1번째 집에 택배 1개를 배달하고, 3번째 집에 택배 3개를 배달합니다.
남은 배달/수거	0/0	0/0	0/0	0/0	0/0	3번째 집에서 물류창고까지 이동하면서(거리 3) 2번째 집에서 빈 택배 상자 3개를 수거한 후, 수거한 빈 택배 상자를 물류창고에 내립니다.

 

16(=5+5+3+3)의 거리를 이동하면서 모든 배달 및 수거를 마쳤습니다. 같은 거리로 모든 배달 및 수거를 마치는 다른 방법이 있지만, 이보다 짧은 거리로 모든 배달 및 수거를 마치는 방법은 없습니다.

 

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

 

---

제한사항

• 1 ≤ cap ≤ 50
• 1 ≤ n ≤ 100,000
• deliveries의 길이 = pickups의 길이 = n
  • deliveries[i]는 i+1번째 집에 배달할 재활용 택배 상자의 개수를 나타냅니다.
  • pickups[i]는 i+1번째 집에서 수거할 빈 재활용 택배 상자의 개수를 나타냅니다.
  • 0 ≤ deliveries의 원소 ≤ 50
  • 0 ≤ pickups의 원소 ≤ 50
• 트럭의 초기 위치는 물류창고입니다.

 

---

 

입출력 예

cap	n	deliveries	pickups	result
4	5	[1, 0, 3, 1, 2]	[0, 3, 0, 4, 0]	16
2	7	[1, 0, 2, 0, 1, 0, 2]	[0, 2, 0, 1, 0, 2, 0]	30

 

---

입출력 예 설명

 

입출력 예 #1

• 문제 예시와 동일합니다.

 

입출력 예 #2

 

 

배달 및 수거할 재활용 택배 상자 개수

	집 #1	집 #2	집 #3	집 #4	집 #5	집 #6	집 #7
배달	1개	0개	2개	0개	1개	0개	2개
수거	0개	2개	0개	1개	0개	2개	0개

 

배달 및 수거 과정

 

	집 #1	집 #2	집 #3	집 #4	집 #5	집 #6	집 #7	설명
남은 배달/수거	1/0	0/2	2/0	0/1	1/0	0/2	2/0	물류창고에서 택배 2개를 트럭에 실어 출발합니다.
남은 배달/수거	1/0	0/2	2/0	0/1	1/0	0/2	0/0	물류창고에서 7번째 집까지 이동하면서(거리 7) 7번째 집에 택배 2개를 배달합니다.
남은 배달/수거	1/0	0/2	2/0	0/1	1/0	0/0	0/0	7번째 집에서 물류창고까지 이동하면서(거리 7) 6번째 집에서 빈 택배 상자 2개를 수거한 후, 수거한 빈 택배 상자를 물류창고에 내리고 택배 2개를 트럭에 싣습니다.
남은 배달/수거	1/0	0/2	1/0	0/1	0/0	0/0	0/0	물류창고에서 5번째 집까지 이동하면서(거리 5) 3번째 집에 택배 1개를 배달하고, 5번째 집에 택배 1개를 배달합니다.
남은 배달/수거	1/0	0/1	1/0	0/0	0/0	0/0	0/0	5번째 집에서 물류창고까지 이동하면서(거리 5) 4번째 집에서 빈 택배 상자 1개를 수거하고 2번째 집에서 빈 택배 상자 1개를 수거한 후, 수거한 빈 택배 상자를 물류창고에 내리고 택배 2개를 트럭에 싣습니다.
남은 배달/수거	0/0	0/1	0/0	0/0	0/0	0/0	0/0	물류창고에서 3번째 집까지 이동하면서(거리 3) 1번째 집에 택배 1개를 배달하고, 3번째 집에 택배 1개를 배달합니다.
남은 배달/수거	0/0	0/0	0/0	0/0	0/0	0/0	0/0	3번째 집에서 물류창고까지 이동하면서(거리 3) 2번째 집에서 빈 택배 상자 1개를 수거한 후, 수거한 빈 택배 상자를 물류창고에 내립니다.

 

30(=7+7+5+5+3+3)의 거리를 이동하면서 모든 배달 및 수거를 마쳤습니다. 같은 거리로 모든 배달 및 수거를 마치는 다른 방법이 있지만, 이보다 짧은 거리로 모든 배달 및 수거를 마치는 방법은 없습니다.
따라서, 30을 return 하면 됩니다.

 

 

 

나의 코드

class Solution {
    public long solution(int cap, int n, int[] deliveries, int[] pickups) {
        long answer = 0;
        int dIdx = deliveries.length-1;
        int pIdx = pickups.length-1;
        
        // 처음에 배달 할 개수가 0보다 큰 집의 인덱스 찾아 세팅
        while(dIdx >= 0 && deliveries[dIdx] == 0) dIdx--;
        
        // 처음에 수거 할 개수가 0보다 큰 집의 인덱스 찾아 세팅
        while(pIdx >= 0 && pickups[pIdx] == 0) pIdx--;
        
        while(dIdx >= 0 || pIdx >= 0) {
            answer += Math.max(dIdx + 1, pIdx + 1) * 2; // 이번에 가야 할 집 중에 제일 먼 집까지의 왕복 거리
            
            int delivery = cap; // 한 번에 트럭이 배달 할 수 있는 개수
            while(dIdx >= 0 && delivery >= 0) {
                if(deliveries[dIdx] > delivery) { // 해당 집의 배달 할 개수가 더 크면 해당 개수만큼만 배달하고 종료 
                    deliveries[dIdx] -= delivery;
                    break;
                } else { // 해당 집의 배달 할 개수가 더 작으면 해당 개수만큼 제거하고 그 앞의 집도 탐색 
                    delivery -= deliveries[dIdx];
                    deliveries[dIdx] = 0;
                    dIdx--;
                }
            }
            
            int pickup = cap;
            while(pIdx >= 0 && pickup >= 0) {
                if(pickups[pIdx] > pickup) {
                    pickups[pIdx] -= pickup;
                    break;
                } else {
                    pickup -= pickups[pIdx];
                    pickups[pIdx] = 0;
                    pIdx--;
                }
            }
        }
        
        return answer;
    }
}

 

풀이

1. 한 번 배달을 갔다 올 때 배달 해야하는 집이나 수거 해야하는 집 중에서 더 먼 곳까지 갔다가 오면서 먼 곳부터 cap의 크기만큼 최대한 배달하고 먼 곳부터 cap의 크기만큼 최대한 수거해 오는 것을 반복하여 배달과 수거를 모두 완료하면 된다.
2. deliveries의 인덱스를 나타낼 dIdx와 pickups의 인덱스를 나타낼 pIdx를 선언하고 각각 deliveries의 마지막 인덱스와 pickups의 마지막 인덱스로 초기화한다.
3. deliveries의 마지막 인덱스의 값과 pickups의 마지막 인덱스의 값이 0일 수도 있으므로 값이 0이 아닐 때까지 감소시켜 값이 있는 제일 먼 곳의 인덱스가 되도록 한다.
4. dIdx와 pIdx가 둘 다 0보다 작아지면 종료되는 while문을 생성한다.
5. while문이 돌 때마다 집의 번호는 1부터 시작이므로 dIdx와 pIdx 중 큰 값에 1을 더해주고 왕복이므로 *2를 하여 answer에 더해주도록 한다.
6. 그리고 cap만큼 배달을 해주기 위해 int형 delivery를 cap의 크기로 초기화 하고 배달을 위한 while문을 생성하여 dIdx가 0 이상이고 delivery가  0 이상이면(배달할 수 있는 개수가 남아있다면) deliveries[dIdx]와 delivery을 비교하여 배달을 한다.
   1. deliveries[dIdx]가 delivery보다 크다면 해당 집에만 배달을 해도 더 해야하므로 deliveries[dIdx]를 delivery만큼을 빼고 해당 배달 while문을 종료한다.
   2. deliveries[dIdx]가 delivery 이하라면 delivery를 deliveries[dIdx]만큼을 뺀 후에 해당 집은 배달을 끝냈으므로 deliveries[dIdx] = 0으로 변경한 후에 dIdx를 1 감소시킨 후 남은 deliverywhile문을 반복한다.
7.  마찬가지로 cap만큼 수거를 해주기 위해 int형 pickup을 cap의 크기로 초기화 하고 수거를 위한 while문을 생성하여 pIdx가 0 이상이고 pickup이 0 이상이면(수거할 수 있는 개수가 남아있다면) pickups[pIdx]와 pickup을 비교하여 수거를 한다.
8. 이렇게 한 번 왕복 할 때마다 배달이나 수거를 해야 할 집 중 가장 먼 곳까지 갔다 오면서 cap의 크기만큼 배달과 수거를 최대한 했으므로 매번 answer에 더해준 왕복 거리 answer가 최소 이동 거리가 된다.