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

1. 문제

성능 요약

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

구분

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

 

문제 설명

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

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

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

 

2. 접근

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

 

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

 

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

 

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

 

3. 전체 코드

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;
    }
}

 

 

4. 회고

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

 

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

 

1. 0 데이터는 뛰어넘기

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

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

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

 

2. While문의 종료 조건

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

 

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

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

 

3. 엣지 케이스

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

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

if(!isChange){
                return 0;
            }

 

 

5. 더 괜찮은 방법

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

 

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

#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;
}