택배 배달과 수거하기(2023 KAKAO BLIND RECRUITMENT)

문제

코드

class Solution {
    public long solution(int cap, int n, int[] deliveries, int[] pickups) {
        long answer = 0;
        while(n>0){
            if(deliveries[n-1]==0&&pickups[n-1]==0){
                n--;
                continue;
            }
            else{
                int truck=0;
                for(int i=1;n-i>=0;i++){
                    if(deliveries[n-i]==0) continue;
                    if(truck+deliveries[n-i]>cap){
                        deliveries[n-i]-=cap-truck;
                        break;
                    }
                    else{
                        truck+=deliveries[n-i];
                        deliveries[n-i]=0;
                    } 
                }
                truck=0;
                for(int i=1;n-i>=0;i++){
                    if(pickups[n-i]==0) continue;
                    if(truck+pickups[n-i]>cap){
                        pickups[n-i]-=cap-truck;
                        break;
                    }
                    else{
                        truck+=pickups[n-i];
                        pickups[n-i]=0;
                    } 
                }
            }
            answer+=n*2;
        }
        
        return answer;
    }
}

풀이

(1) 기본적인 공식은 가장 먼곳에 있는곳의 배달과 수거를 먼저 완료해야 한다는 것이다.(Greedy)
(2) 가장 먼 집부터 배달해야하거나 수거해야할 상자가 있는지 확인한다. 있다면, 가장 먼 곳부터, 배달할 수 있는(cap만큼) 모든 택배를 deliveries 배열에서 차감시킨다. 또한, 같은 방법으로 수거할 수 있는 모든 상자를 pickups 배열에서 차감시킨다. (가는 길에 가장 먼 집을 기준으로 배달할 수 있는만큼 최대한 택배를 배달하고, 오는길에 수거할 수 있는만큼 최대한 수거하면서 돌아온다고 이해하면 편하다.)
배달하거나 수거할 상자가 없다면, 다음 집을 확인한다.
(3) 배달하거나 수거할 상자가 있을때마다, 위의 과정을 거친다. 이는 그 집까지 갔다 왔다는 것이므로, 방문한 집의 거리*2만큼 answer에 더해준다.

결과

처음에 문제를 읽고, 좀 어렵다는 생각이 들었다. 제한사항을 보니, 완전탐색도 아닌것 같고, 딱히 dp로도 풀 수 없을 것 같고 하니 그리디 알고리즘일거라는 생각은 들었다.
가장 먼 집부터 처리해버린다는 아이디어 자체는 맞았지만, 내가 구현을 하는 과정에서 많은 결함이 있었기 때문에 자꾸 정확성 테스트에서 떨어졌다.
좀 더 정리를 완벽하게 하고 구현에 들어갔으면, 시간을 많이 줄였을텐데 살짝 아쉬웠다.

출처 : 프로그래머스 코딩 테스트 연습 https://school.programmers.co.kr/learn/challenges