[프로그래머스] 택배 배달과 수거하기

보자마자 그리디라고 생각한 문제.

그리디로 풀었다고 생각했는데 내가 생각한 건 매우 복잡한 코드였고,

정말 쉽게 푸는 방법이 있어서 블로그를 작성한다...

 

내가 푼 코드

import java.util.*;

class Solution {
    public long solution(int cap, int n, int[] deliveries, int[] pickups) {
        long answer = 0;
        Queue<Integer> queue = new ArrayDeque<>();
        
        for(int i = n - 1; i >= 0; i--) {
            if(deliveries[i] != 0 || pickups[i] != 0) {
                queue.add(i);
            }
        }
        
        while(!queue.isEmpty()) {
            int idx = queue.peek();
            if(deliveries[idx] == 0 && pickups[idx] == 0) {
                queue.poll();
                continue;
            }
            
            answer += idx + 1;
            
            int del = cap;
            int pick = cap;
            for(int i = idx; i >= 0; i--) {
                int sub = Math.min(del, deliveries[i]);
                deliveries[i] -= sub;
                del -= sub;
                if(del == 0) break;
            }
            
            for(int i = idx; i >= 0; i--) {
                int sub = Math.min(pick, pickups[i]);
                pickups[i] -= sub;
                pick -= sub;
                if(pick == 0) break;
            }
        }
        
        return answer * 2;
    }
}

 

쉽게 푸는 풀이

import java.util.*;

class Solution {
    public long solution(int cap, int n, int[] deliveries, int[] pickups) {
        long answer = 0;
        int deliver = 0;  // 배달 가능한 개수
        int pickup = 0;   // 수거 가능한 개수
        
        // 가장 먼 집부터 처리
        for (int i = n - 1; i >= 0; i--) {
            deliver += deliveries[i];
            pickup += pickups[i];
            
            // 현재 위치에 배달이나 수거할 것이 있다면
            while (deliver > 0 || pickup > 0) {
                // 한 번의 이동으로 최대 cap개씩 처리
                deliver -= cap;
                pickup -= cap;
                // i+1 위치까지 왕복 거리 추가
                answer += (i + 1) * 2L;
            }
        }
        
        return answer;
    }
}

 

내가 푼 풀이는 큐가 빌 때까지 for문을 계속해서 돌아야하지만,

쉽게 푸는 풀이는 for문을 한 번만 돌면 끝나는 구조.

 

쉬운 문제는 쉽게 생각할 수 있어야 하는데, 그게 어려운 것 같다.