[2023 KAKAO BLIND RECRUITMENT] 택배 배달과 수거하기

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

프로그래머스

 

우선 이동 거리를 최소로 하기 위해서는 물류창고로부터 멀리 떨어진 집을 우선으로 배달/수거를 해야 한다. (그리디 알고리즘)

 

따라서 배달할 수 있는 상자의 수를 d, 수거할 수 있는 상자의 수를 p라고 하면, 다음과 같이 구현할 수 있다.

int d = cap;
int p = cap;
 
// 가장 먼 집부터 배달/수거
for (int i = n - 1; i >= 0; i--) {
    d -= deliveries[i];
    p -= pickups[i];
}

 

그러다가 배달해야 하는데 트럭에 배달할 수 있는 상자가 없거나 수거해야 하는데 트럭에 수거 상자를 둘 공간이 없으면, 물류창고로 이동해야 한다. 그리고 이는 코드로 d가 음수이거나 p가 음수인 상황이다.

 

그리고 d가 음수이거나 p가 음수이면, 물류창고로 돌아가 상자를 다시 싣고 해당 위치(i)로 반드시 다시 돌아와야 한다. 해당 위치에 배달해야 할 상자 또는 수거해야 할 상자가 남아있기 때문이다(그렇기 때문에 p나 d가 음수가 된 것이다).

 

따라서 d가 음수이거나 p가 음수이면, 물류창고에서 배달할 상자를 새로 cap만큼 실었다는 것을 반영하기 위해 p와 d에 cap을 더해준다. 그리고 해당 위치(i)로 다시 돌아와 배달/수거를 진행한 것이기 때문에 answer에 (i + 1) * 2를 더해준다.

 

그리고 d와 p에 cap만큼 더해줄 때, d와 p 둘 중 하나라도 음수이면 안된다. 이는 아직 해당 위치에 배달/수거할 상자가 남아있는데 트럭이 그에 충족하지 못하는 상태라는 의미이기 때문이다. 따라서 d와 p가 모두 0 이상이 될 때까지 cap만큼 더해준다. 

 

그리고 p와 d에 cap만큼 더해준다는 것은 다음 논리를 포함한다.

• 배달을 하고 물류창고로 돌아오는 길에 수거를 할 수 있다. 예를 들어, deliveries와 pickups가 다음과 같고 cap이 2라고 가정하자. 이때 3번 집에 상자 2개를 배달하고, 돌아오는 길에 2번 집의 상자 2개를 수거할 수 있다.

	1번 집	2번 집	3번 집
배달	0	0	2
수거	0	2	0

 

• 반대도 마찬가지다. 수거를 하러 가는 길에 배달을 할 수 있다. 예를 들어, deliveries와 pickups가 다음과 같고 cap이 2라고 가정하자. 이때 3번 집에 상자 2개를 수거하러 가는 길에, 2번 집에 상자 2개를 먼저 배달하고 3번 집에 가서 상자 2개를 수거할 수 있다.

	1번 집	2번 집	3번 집
배달	0	2	0
수거	0	0	2

 

따라서 만약 deliveries와 pickups가 다음과 같고 cap이 2라고 가정할 때, 5번 집에 가서 상자를 배달하고, 돌아오는 길에 4번 집의 상자를 수거할 수 있다. 그리고 이어서 3번 집에 상자 2개를 배달하고, 돌아오는 길에 2번 집과 1번 집의 상자를 모두 수거할 수 있다. 따라서 답은 5 * 2 + 3 * 2 = 16이 된다.

	1번 집	2번 집	3번 집	4번 집	5번 집
배달	0	0	2	0	2
수거	1	1	0	2	0

 

이를 코드로 보면 다음과 같다.

	i = 4 (5번 집)	i = 3 (4번 집)	i = 2 (3번 집)	i = 1 (2번 집)	i = 0 (1번 집)
d (초기 값 = 2)	0	0	-2 ➡️ 0	0	0
p (초기 값 = 2)	2	0	0 ➡️ 2	1	0

 

• 이때 i = 2 부분에 주목하자.
• 4번 집까지 처리한 후에 3번 집에 왔을 때는 배달할 수 있는 상자가 0개이고, 배달해야 할 상자는 2개이다. 따라서 d가 -2가 된다. 
• d가 음수이므로, d와 p에 cap인 2만큼 더해준다. 그러면 d는 0, p는 2가 된다.
• 이때 당장 3번 집에서 수거해야 할 상자는 없지만 그럼에도 p += cap을 진행했다. 그리고 이때 p에 cap을 더해준 것은 2번 집과 1번 집의 상자를 수거할 때 반영된다.
• 즉, 3번 집에 상자 2개를 배달하고, 다시 물류창고에 들릴 필요 없이 돌아가는 길에 2번 집과 1번 집의 상자를 수거한다는 의미이다. 

class Solution {
    public long solution(int cap, int n, int[] deliveries, int[] pickups) {

        long answer = 0;
        int delivery = cap;
        int pickup = cap;

        for(int i = n - 1; i >= 0; i--) {
            if(deliveries[i] != 0 || pickups[i] != 0) {
                answer += (i + 1) * 2;
                break;
            }
        }

        for(int i = n - 1; i >= 0; i--) {
            if(deliveries[i] == 0 && pickups[i] == 0) {
                continue;
            }
            
            delivery -= deliveries[i];
            pickup -= pickups[i];

            while (delivery < 0 || pickup < 0) {
                answer += (i+1) * 2;
                delivery += cap;
                pickup += cap;
            }
        }

        return answer;
    }
}

또 다른 풀이

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];
            
            // d와 p 둘 중 하나라도 음수이면 물류창고 다녀와야 함
            int cnt = 0;
            while (d < 0 || p < 0) {
                d += cap;
                p += cap;
                cnt++;
            }
            
            answer += (i + 1) * cnt * 2;
        }
        
        return answer;
    }
}