[자바] 2023 카카오 블라인드 채용 : 택배 배달과 수거하기 풀이 (그리디)

https://school.programmers.co.kr/learn/courses/30/lessons/150369?language=java 

프로그래머스

Level2, 782 solve 정답률 22% 그리디 문제입니다.

개인적으로 시간이 많이 들었고 그리디한 방법을 찾기 어려운 문제였다고 생각합니다.🥲

---

문제 풀이 및 접근

문제 이해 자체는 간단합니다.

택배 배달과 수거를 동시에 진행을 하는데, 택배 차량은 한 번에 cap개의 상자를 실을 수 있습니다.

​

따라서 n개의 집을 돌아다니면서 배송 및 수거를 하면서 cap개를 맞춰서(최대의 개수를 가지고 이동) 최적의 이동 거리를 구하면 되는 문제입니다.

​

저는 이 문제를 보고나서 배달/수거의 거리를 최소로 해야한다는 점과 자바로 풀기 전 문제를 머리로 풀었을 때 마지막 장소부터 처리해줘야함을 알고 그리디로 접근했습니다.

​

마지막부터 처리해야하는 이유는 어차피 마지막(가장 먼 곳)부터 처리를 해준다면 배달/수거의 구분 없이 문제를 해결할 수 있기 때문입니다.

​

덧 붙여서 마지막 장소부터 수거 및 회수를 해줘야지 돌아오면서 cap의 저장공간이 남았다면 더 빼올 수 있기 때문입니다. 어차피 배달/수거의 수는 정해져있기 때문입니다.

​

for문을 통해서 가장 먼 집부터 탐색을 한 후에 탐색 지역의 배달/수거의 수를 변수에 저장해주었고,

그 후에 while문을 통해서 배달/수거의 수가 둘다 0이하라면 전부 배달/수거를 한 것으로 간주하고 while문을 탈출 시킨 후 두 번째로 먼 집을 탐색하는 식으로 진행을 했습니다.

​

이 방법 말고도 스택으로도 풀 수 있을 것 같습니다.

스택인 경우는 가까운 순서부터 스택에 담아주고, 마지막에 담긴 두 스택(배달/수거)의 집 번호를 비교해서 answer에 거리를 더해주는 방법으로 진행하다가, 스택이 빌 때까지 처리를 해주는 방식으로 풀 수도 있을 것 같습니다.

 

---

public class Solution {
    public static long solution(int cap, int n, int[] deliveries, int[] pickups) {
        long answer = 0;

        // 1. 데이터 세팅 (먼 곳부터 탐색해야하므로 역순 저장)
        int sizeOfLastDeliveries = 0;
        int sizeOfLastPickups = 0;

        List<Integer> reverseDeliveries = new ArrayList<>();
        List<Integer> reversePickups = new ArrayList<>();

        for (int i = n - 1; i >= 0; i--) {
            reverseDeliveries.add(deliveries[i]);
            reversePickups.add(pickups[i]);
        }

        // 2. 먼곳부터 순차적으로 남은 배달 혹은 픽업 건에 추가
        // 2-1. while -> 남은 배달 혹은 픽업이 0이 될 때까지 빼주고, 거리 * 2
        for (int i = 0; i < n; i++) {
            sizeOfLastDeliveries += reverseDeliveries.get(i);
            sizeOfLastPickups += reversePickups.get(i);

            while (true) {
                if(sizeOfLastDeliveries <= 0 && sizeOfLastPickups <= 0) {
                    break;
                }
                sizeOfLastDeliveries -= cap;
                sizeOfLastPickups -= cap;
                answer += (n - i) * 2;
            }
        }

        return answer;
    }
}