[알고리즘][X] 택배 배달과 수거하기

문제 설명
재할용 택배 상자.png

당신은 일렬로 나열된 n개의 집에 택배를 배달하려 합니다. 배달할 물건은 모두 크기가 같은 재활용 택배 상자에 담아 배달하며, 배달을 다니면서 빈 재활용 택배 상자들을 수거하려 합니다.
배달할 택배들은 모두 재활용 택배 상자에 담겨서 물류창고에 보관되어 있고, i번째 집은 물류창고에서 거리 i만큼 떨어져 있습니다. 또한 i번째 집은 j번째 집과 거리 j - i만큼 떨어져 있습니다. (1 ≤ i ≤ j ≤ n)
트럭에는 재활용 택배 상자를 최대 cap개 실을 수 있습니다. 트럭은 배달할 재활용 택배 상자들을 실어 물류창고에서 출발해 각 집에 배달하면서, 빈 재활용 택배 상자들을 수거해 물류창고에 내립니다. 각 집마다 배달할 재활용 택배 상자의 개수와 수거할 빈 재활용 택배 상자의 개수를 알고 있을 때, 트럭 하나로 모든 배달과 수거를 마치고 물류창고까지 돌아올 수 있는 최소 이동 거리를 구하려 합니다. 각 집에 배달 및 수거할 때, 원하는 개수만큼 택배를 배달 및 수거할 수 있습니다.

다음은 cap=4 일 때, 최소 거리로 이동하면서 5개의 집에 배달 및 수거하는 과정을 나타낸 예시입니다.

배달 및 수거할 재활용 택배 상자 개수

집 #1	집 #2	집 #3	집 #4	집 #5
배달	1개	0개	3개	1개	2개
수거	0개	3개	0개	4개	0개
배달 및 수거 과정

집 #1	집 #2	집 #3	집 #4	집 #5	설명
남은 배달/수거	1/0	0/3	3/0	1/4	2/0	물류창고에서 택배 3개를 트럭에 실어 출발합니다.
남은 배달/수거	1/0	0/3	3/0	0/4	0/0	물류창고에서 5번째 집까지 이동하면서(거리 5) 4번째 집에 택배 1개를 배달하고, 5번째 집에 택배 2개를 배달합니다.
남은 배달/수거	1/0	0/3	3/0	0/0	0/0	5번째 집에서 물류창고까지 이동하면서(거리 5) 4번째 집에서 빈 택배 상자 4개를 수거한 후, 수거한 빈 택배 상자를 물류창고에 내리고 택배 4개를 트럭에 싣습니다.
남은 배달/수거	0/0	0/3	0/0	0/0	0/0	물류창고에서 3번째 집까지 이동하면서(거리 3) 1번째 집에 택배 1개를 배달하고, 3번째 집에 택배 3개를 배달합니다.
남은 배달/수거	0/0	0/0	0/0	0/0	0/0	3번째 집에서 물류창고까지 이동하면서(거리 3) 2번째 집에서 빈 택배 상자 3개를 수거한 후, 수거한 빈 택배 상자를 물류창고에 내립니다.
16(=5+5+3+3)의 거리를 이동하면서 모든 배달 및 수거를 마쳤습니다. 같은 거리로 모든 배달 및 수거를 마치는 다른 방법이 있지만, 이보다 짧은 거리로 모든 배달 및 수거를 마치는 방법은 없습니다.

트럭에 실을 수 있는 재활용 택배 상자의 최대 개수를 나타내는 정수 cap, 배달할 집의 개수를 나타내는 정수 n, 각 집에 배달할 재활용 택배 상자의 개수를 담은 1차원 정수 배열 deliveries와 각 집에서 수거할 빈 재활용 택배 상자의 개수를 담은 1차원 정수 배열 pickups가 매개변수로 주어집니다. 이때, 트럭 하나로 모든 배달과 수거를 마치고 물류창고까지 돌아올 수 있는 최소 이동 거리를 return 하도록 solution 함수를 완성해 주세요.

제한사항
1 ≤ cap ≤ 50
1 ≤ n ≤ 100,000
deliveries의 길이 = pickups의 길이 = n
deliveries[i]는 i+1번째 집에 배달할 재활용 택배 상자의 개수를 나타냅니다.
pickups[i]는 i+1번째 집에서 수거할 빈 재활용 택배 상자의 개수를 나타냅니다.
0 ≤ deliveries의 원소 ≤ 50
0 ≤ pickups의 원소 ≤ 50
트럭의 초기 위치는 물류창고입니다.
입출력 예
cap	n	deliveries	pickups	result
4	5	[1, 0, 3, 1, 2]	[0, 3, 0, 4, 0]	16
2	7	[1, 0, 2, 0, 1, 0, 2]	[0, 2, 0, 1, 0, 2, 0]	30
입출력 예 설명
입출력 예 #1

문제 예시와 동일합니다.
입출력 예 #2

배달 및 수거할 재활용 택배 상자 개수

집 #1	집 #2	집 #3	집 #4	집 #5	집 #6	집 #7
배달	1개	0개	2개	0개	1개	0개	2개
수거	0개	2개	0개	1개	0개	2개	0개
배달 및 수거 과정

집 #1	집 #2	집 #3	집 #4	집 #5	집 #6	집 #7	설명
남은 배달/수거	1/0	0/2	2/0	0/1	1/0	0/2	2/0	물류창고에서 택배 2개를 트럭에 실어 출발합니다.
남은 배달/수거	1/0	0/2	2/0	0/1	1/0	0/2	0/0	물류창고에서 7번째 집까지 이동하면서(거리 7) 7번째 집에 택배 2개를 배달합니다.
남은 배달/수거	1/0	0/2	2/0	0/1	1/0	0/0	0/0	7번째 집에서 물류창고까지 이동하면서(거리 7) 6번째 집에서 빈 택배 상자 2개를 수거한 후, 수거한 빈 택배 상자를 물류창고에 내리고 택배 2개를 트럭에 싣습니다.
남은 배달/수거	1/0	0/2	1/0	0/1	0/0	0/0	0/0	물류창고에서 5번째 집까지 이동하면서(거리 5) 3번째 집에 택배 1개를 배달하고, 5번째 집에 택배 1개를 배달합니다.
남은 배달/수거	1/0	0/1	1/0	0/0	0/0	0/0	0/0	5번째 집에서 물류창고까지 이동하면서(거리 5) 4번째 집에서 빈 택배 상자 1개를 수거하고 2번째 집에서 빈 택배 상자 1개를 수거한 후, 수거한 빈 택배 상자를 물류창고에 내리고 택배 2개를 트럭에 싣습니다.
남은 배달/수거	0/0	0/1	0/0	0/0	0/0	0/0	0/0	물류창고에서 3번째 집까지 이동하면서(거리 3) 1번째 집에 택배 1개를 배달하고, 3번째 집에 택배 1개를 배달합니다.
남은 배달/수거	0/0	0/0	0/0	0/0	0/0	0/0	0/0	3번째 집에서 물류창고까지 이동하면서(거리 3) 2번째 집에서 빈 택배 상자 1개를 수거한 후, 수거한 빈 택배 상자를 물류창고에 내립니다.
30(=7+7+5+5+3+3)의 거리를 이동하면서 모든 배달 및 수거를 마쳤습니다. 같은 거리로 모든 배달 및 수거를 마치는 다른 방법이 있지만, 이보다 짧은 거리로 모든 배달 및 수거를 마치는 방법은 없습니다.
따라서, 30을 return 하면 됩니다.

나의 풀이

- 전체적인 로직의 흐름은 맞았으나 while or and를 잘 못써서 틀림

- 또한 에지 케이스 핸들링을 제대로 안해줬음

- 예를 들어, 처음 while문에서 deliveries의 값이 0이면 인덱스를 줄이는 식으로 했는데 이렇게 되면 처음부터 모든게 0이면 last_deliveries가 -n을 넘어서고 그렇게 되면 런타임 에러가 남

- while 문에서 둘다 만족안되면으로 하려면 or로 해야 한다. 하나라도 만족이 안되면은 and이다. 헷갈리지 말자!!!

배열의 유효한 인덱스는 -len(arr)에서부터 len(arr)-1까지입니다.

- 그렇다고 챗지피티가 답변해줌

- while문은 중복이 되기에 함수로 바꿔줄 수 있음

def solution(cap, n, deliveries, pickups):
    # 최소이므로 그리디, DP, 탐색
    # 무작정 탐색을 하게 되면 시간 초과 나므로 탐색 X
    # 중간 결과를 활용할 방법이 없으므로 DP X
    # 따라서 그리디
    # 최선의 선택은 제일 뒤부터 배달하고 수거를 하는 것이다.
    # 배달할 제일 뒤엣집, 수거할 제일 뒤엣집 중 더 큰 값까지 이동한다.
    # 뒤에부터 배달하여 값을 갱신하고 수거하여 값을 갱신한다.
    # 이때 거리 = 제일 뒤 * 2이다.
    
    last_deliveries = n - 1
    last_pickups = n - 1
    moving_distance = 0
    while last_deliveries >= 0 and deliveries[last_deliveries] == 0:
        last_deliveries -= 1
    while last_pickups >= 0 and pickups[last_pickups] == 0:
        last_pickups -= 1
    while last_deliveries >= 0 or last_pickups >= 0:
        
        # print(2 * (max(last_deliveries, last_pickups) + 1))
        moving_distance += 2 * (max(last_deliveries, last_pickups) + 1)
        
        ct = cap
        while last_deliveries >= 0:
            if ct >= deliveries[last_deliveries]:
                ct -= deliveries[last_deliveries]
                last_deliveries -= 1
            else:
                deliveries[last_deliveries] -= ct
                break
        ct = cap
        while last_pickups >= 0:
            if ct >= pickups[last_pickups]:
                ct -= pickups[last_pickups]
                last_pickups -= 1
            else:
                pickups[last_pickups] -= ct
                break

    answer = moving_distance    
    return answer

- 아래는 공통되는 부분을 함수로 리팩토링한 코드이다. 결과적으로 훨씬 깔끔해지고 함수만 바꾸면 되기 때문에 디버그하기도 용이해진다고 볼 수 있다. 이렇게 함수로 만들 수 있는 건 함수로 만들도록 해보자!!

def solution(cap, n, deliveries, pickups):
    # 최소이므로 그리디, DP, 탐색
    # 무작정 탐색을 하게 되면 시간 초과 나므로 탐색 X
    # 중간 결과를 활용할 방법이 없으므로 DP X
    # 따라서 그리디
    # 최선의 선택은 제일 뒤부터 배달하고 수거를 하는 것이다.
    # 배달할 제일 뒤엣집, 수거할 제일 뒤엣집 중 더 큰 값까지 이동한다.
    # 뒤에부터 배달하여 값을 갱신하고 수거하여 값을 갱신한다.
    # 이때 거리 = 제일 뒤 * 2이다.
    def delivery_and_take(cap, array, last_index):
        ct = cap
        while last_index >= 0:
            if ct >= array[last_index]:
                ct -= array[last_index]
                last_index -= 1
            else:
                array[last_index] -= ct
                break
        return last_index
    
    def find_last_index_at_first(array, last_index):
        while last_index >= 0 and array[last_index] == 0:
            last_index -= 1
        return last_index
        
    last_deliveries = n - 1
    last_pickups = n - 1
    moving_distance = 0
    
    last_deliveries = find_last_index_at_first(deliveries, last_deliveries)
    last_pickups = find_last_index_at_first(pickups, last_pickups)
        
    while last_deliveries >= 0 or last_pickups >= 0:
        moving_distance += 2 * (max(last_deliveries, last_pickups) + 1)
        
        last_deliveries = delivery_and_take(cap, deliveries, last_deliveries)
        last_pickups = delivery_and_take(cap, pickups, last_pickups)
        
    answer = moving_distance    
    return answer

- 참고로 아래와 같이 아주 간결한 풀이도 가능하다.

def solution(cap, n, deliveries, pickups):
    deliveries = deliveries[::-1]
    pickups = pickups[::-1]
    answer = 0

    have_to_deli = 0
    have_to_pick = 0

    for i in range(n):
        have_to_deli += deliveries[i]
        have_to_pick += pickups[i]

        while have_to_deli > 0 or have_to_pick > 0:
            have_to_deli -= cap
            have_to_pick -= cap
            answer += (n - i) * 2

    return answer

 

Reference

---

https://oh2279.tistory.com/147

[프로그래머스/python] Level 2 : 택배 배달과 수거하기