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

2023 KAKAO BLIND RECUITMENT 택배 배달과 수거하기 문제를 풀어보았다.

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

프로그래머스

---

문제 설명

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

일렬로 나열된 집에 택배를 배달하면서, 수거해야 할 물건이 있으면 수거해와야 한다. 트럭에 실을 수 있는 양은 정해져 있고, 처음 생각한 것은 멀리 있는 곳부터 최대한 배달을 하고, 최대한 물건을 수거해 온다.라고 생각을 하여 그리디 알고리즘이 필요하겠다고 생각했다.

 

예시

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

하지만 또 생각해봐야할 것이.. 택배를 꽉꽉 채워서 가버리면, 수거를 못하는 경우가 있어 다시 왔다 갔다 하는 문제가 생길 수 있을 것 같다고 생각했다.

-> 가는 길에 배달할 택배를 배달하고, 마지막으로 맨 끝집에 배달해버리면? 다른 집 택배 때문에 왔다 갔다 할 일은 없다.

 

제한사항 및 입출력 예

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

 n의 개수가 10만개이니까.. O(N)에 풀어야겠다고 판단하고, 맨 마지막 집부터 처리하는 생각으로 접근을 했다.

하지만, 최소 이동거리를 생각하면, 가능하다면 미리 옮길 수 있는 택배를 옮기고, 수거하면서 진행해야 한다.

이를 잘 이용해서 구현해야하는 문제였다.

 

---

풀이 코드

import java.util.*;
class Solution {
    public long solution(int cap, int n, int[] deliveries, int[] pickups) {
        long answer = 0;
        int d = 0;
        int p = 0;
        for(int i=n-1; i>=0; i--){
            d -= deliveries[i];
            p -= pickups[i];
            int cnt = 0;
            while(d < 0 || p < 0){
                d += cap;	// 한 번에 최대한 배달하여 가는 도중에 다른집에 반환했다 생각
                p += cap;	// 한 번에 최대한 수거하여 돌아 오는 도중에 다른집에서 수거했다 생각
                cnt +=1;
            }
            answer += (i+1)*2*cnt;	// 왕복 거리
        }
        return answer;
    }
}

제일 멀리 있는 집부터 방문하면서, 가는 도중에 남는 공간이 있다면 배달, 수거할 수 있기 때문에 1회 왕복마다 최대 용량 cap을 더해주면 깔끔하게 풀 수 있다.

---

 요즘 문제를 보면 이분탐색을 통한 가장 적합한 값을 찾는다거나, 반복문 두 개를 이용한 풀이를 한 개로 풀 수 있도록 구현해 내는 문제들이 많은 것 같다. 이런 문제들을 풀다 보면 아이디어가 적립되는 기분이다.. 좋은 풀이라고 생각하며 잘 기억해 뒀다가 비슷한 상황에 써먹을 수 있어야겠다.