[프로그래머스] 택배 배달과 수거하기 level2 (Java) - 그리디

1. 1. 문제

2. 성능 요약

메모리: 102 MB, 시간: 39.17 ms

3. 구분

코딩테스트 연습 > 2023 KAKAO BLIND RECRUITMENT

 

4. 문제 설명

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

다음은 cap=4 일 때, 최소 거리로 이동하면서 5개의 집에 배달 및 수거하는 과정을 나타낸 예시입니다.

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

 

5. 2. 접근

이런 비슷한 그리디 문제를 풀어봤어서 그리디 문제라는 것을 알고 시작했다. 또한 테스트 케이스 설명을 보면 다들 제일 끝에서부터 가져온다. 또한 생각을 해봤을 때 멀리 있는 곳은 최대한 적은 횟수롤 이동해야 최소가 될 수 있기 때문에  최대한 멀리있는 것을 배달하거나 수거하기로 했다.

 

또한 최대의 효율은 한 번에 cap만큼의 배달과 수거를 진행하는 것이다. 배달과 수거를 진행하는데 별도의 시간이 없기 때문에, cap만큼 택배를 가져가고 내려놓고, cap만큼 수거하면 된다.

 

이 둘의 작업이 연관이 있다고 생각할 수 있는데 사실 전혀 연관이 없다. 어차피 가장 먼 거리를 가게될 것이고, 그 사이에 배달을 먼저하든 수거를 먼저하든 결과는 같다.

 

그래서 가장 멀리 떨어져 있는 배달, 수거 지점을 알 수 있도록 인덱스 변수를 2개 사용하기로 했고 거리를 더 하는 기준은 두 인덱스 중 더 먼것을 더하기로 했다. 왜냐하면 배달과 수거라는 구분에 상관없이 멀리 이동하면 2개의 일을 모두 할 수 있다. 그리고 2개의 일을 반드시 끝까지 해야되기 때문에 더 먼 인덱스를 더하는 것이다.

 

6. 3. 전체 코드

      

      

      

    
    

      <java />
    
import java.util.*;

class Solution {
    public long solution(int cap, int n, int[] deliveries, int[] pickups) {
        long answer = 0;
        // 최대한 멀리있는 것을 배달하면서, 수거해야함 - 인덱스 관리
        
        int dIdx = n-1; // 배달 시작해야하는 인덱스
        int pIdx = n-1; // 수거 시작해야하는 인덱스
        
        int box;
        int pick;
        
        boolean isChange = false;
        
        while(true){
            if(dIdx < 0 && pIdx <0){
                break;
            }
            // 최대한 뒷자리에 배달을 하고, 수거 남은 곳 수거 (왕복거리)
            answer += (Math.max(dIdx +1, pIdx+1))*2;
            
            box = cap;
            pick = cap;
            
            // 택배 끝까지 놓고 오기
            while(dIdx >=0 && box > 0){
            	// 0 인경우 다음 것을 가리켜야 함
                if(deliveries[dIdx] == 0){
                    dIdx--;
                    continue;
                }
                deliveries[dIdx]--;
                box--;
                isChange = true;
                
                if(deliveries[dIdx] == 0){
                    dIdx--;
                }
            }
            
            // 최소 이동을 위해 단축시켜 놓기
            while(dIdx >=0 && deliveries[dIdx] == 0){
                dIdx--;
            }
            
            // 수거 시작
            while(pIdx >=0 && pick > 0){
                if(pickups[pIdx] == 0){
                    pIdx--;
                    continue;
                }
                
                pickups[pIdx]--;
                pick--;
                isChange = true;
                
                if(pickups[pIdx] == 0){
                    pIdx--;
                }
            }
            
            while(pIdx >=0 && pickups[pIdx] == 0){
                pIdx--;
            }
            
            // 모두가 다 0일 때, 이동할 필요없음
            if(!isChange){
                return 0;
            }
        }
        
        
        return answer;
    }
}

 

7.  

8. 4. 회고

아이디어 구상과 접근 방법은 빠르게 했는데, 예외 케이스를 계속 놓쳐서 푸는데까지는 오래걸렸다. 

 

생각못한 예외 케이스는 꽤 많았는데...

 

1. 0 데이터는 뛰어넘기

마지막에 가리키고 있는 위치에 택배, 수거 할 물건이 하나도 없을 때 다음 인덱스를 가리키도록 해야하는데 그러지 않았다.

그래서 배달, 수거를 다 하고나서 현재 인덱스가 0를 가리키지 않도록 로직을 추가 했다.

      

      

      

    
    

      <java />
    
while(dIdx >=0 && deliveries[dIdx] == 0){
                dIdx--;
            }

 

2. While문의 종료 조건

while문에서 && 연산을 사용하면서(조건1) && (조건2), 조건1이 아니고 조건2가 아닐 때까지를 생각하고 사용했는데 ||(or)연산자를 써야했다. 왜냐하면 while문의 탈출 조건은 쉽게 말하면 ~까지로 만족하지 않는 조건을 써줘야 해서 헷갈린다. 그래서 보통 if문 조건의 반대라고 생각해서 사용하는데 이번에 놓쳐서 헤맸다. 

 

확실히 While(true) 해놓고 안쪽에서 if문으로 탈출 조건을 명시하는 것이 실수로 줄이고 생각도 편하다.

      

      

      

    
    

      <java />
    
while(true){
            if(dIdx < 0 && pIdx <0){
                break;
            }
            ....
}

 

3. 엣지 케이스

양 극단의 케이스인 경우를 생각안했다. 수거도 배달도 해야되지 않는 상황을 체크안해서 오답이 나고 있었다.

변화는 감지하는 boolean 변수를 두어서 변화를 체크하고, 변화가 없을 시 바로 0을 리턴하도록 했다.

      

      

      

    
    

      <java />
    
if(!isChange){
                return 0;
            }

 

 

9. 5. 더 괜찮은 방법

다른 사람의 풀이는 어떨까 하고 봤는데, 엄청 간단하게 풀 수도 있구나 했다

 

(출처 : https://school.programmers.co.kr/questions/43364) c++ 

      

      

      

    
    

      <java />
    
#include <bits/stdc++.h>
#include <string>
#include <vector>

using namespace std;

long long solution(int cap, int n, vector<int> deliveries, vector<int> pickups) {
    long long answer = 0;
    int deliverySum = 0;
    int pickupSum = 0;
    
    for(int i = n-1; i >= 0; i--)
    {
        int cnt = 0;
        deliverySum += deliveries[i];
        pickupSum += pickups[i];
        
        while(deliverySum > 0 || pickupSum > 0)
        {
            deliverySum -= cap;
            pickupSum -= cap;
            cnt++;
        }
        answer += (i+1) * 2 * cnt;
    }
    
    return answer;
}