[Programmers] 2023 KAKAO BLIND RECRUITMENT : 택배 배달과 수거하기 (Java)

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

프로그래머스

---

실제 시험에서 못 풀었던 문제다.

그리디와 최적화가 필요한 문제이다. 그리디적인 아이디어를 떠올리긴 어렵지 않지만, 매번 배달 거리를 처음부터 계산하도록 코딩하면 O(N^2) 이다. 인덱스를 기억해서 O(N) 으로 바꿔야 한다.

알고리즘

그리디

배달과 수거를 할 때, 제일 먼 곳부터 배달/수거하면 된다. 조금만 생각해보면 먼 곳부터 다녀오면서 거리를 줄여나가는 것이 최적이라는 것을 생각할 수 있다.

즉, 매 움직임마다 가장 먼 거리를 계산하고 (코드의 lastIdx 메소드) 각 배열마다 배달/수거한 것으로 최신화(코드의 move 메소드)하면 된다.

최적화

이 때, 매 번 배열의 맨 마지막 (n-1) 부터 가장 먼 거리를 계산하면 최악의 경우 (배달은 가장 먼 거리부터 꽉 차있고, 수거할 것은 하나도 없는 경우) O(N^2)이 걸린다. (테스트 케이스 16)

따라서 n-1 부터가 아니라 이전에 계산한 인덱스를 저장해놓고 거기부터 계산하면 어떤 경우에도 O(N)이 소요된다.

정답 코드

class Solution {
    public long solution(int cap, int n, int[] deliveries, int[] pickups) {
        long answer = 0;
        int idx = n-1;
        while (true) {
            idx = lastIdx(idx, deliveries, pickups);
            if (idx == -1) break;
            move(cap, idx, deliveries);
            move(cap, idx, pickups);
            answer += (idx + 1) * 2;
        }
        return answer;
    }
    
    private int lastIdx (int idx, int[] deliveries, int[] pickups) {
        while (deliveries[idx] == 0 && pickups[idx] == 0) {
            idx--;
            if (idx == -1) break;
        }
        return idx;
    }
    
    private void move (int cap, int idx, int[] arr) {
        while (cap > 0 && idx >= 0) {
            int minus = Math.min(cap, arr[idx]);
            cap -= minus;
            arr[idx] -= minus;
            idx--;
        }
    }
}