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

문제 설명

 

 

당신은 일렬로 나열된 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 하면 됩니다.

 

 

1. 문제 풀이

문제의 핵심은 최소 이동 거리를 구하는 것이다. 트럭은 물류창고에서 출발하여 배달을 수행하고, 빈 상자를 수거하여 다시 물류창고로 돌아와야 한다. 트럭에 실을 수 있는 상자의 개수는 cap으로 제한되어 있다.

이 문제를 풀기 위해 가장 먼저 파악해야 할 직관은 다음과 같다.

1. 가장 먼 집부터 처리해야 한다. 물류창고에서 가장 먼 집(n번째 집)에 배달하거나 수거할 물건이 있다면, 트럭은 반드시 그곳까지 이동해야 한다. 기왕 먼 곳까지 이동하는 김에, 오는 길(경로상)에 있는 가까운 집들의 배달 및 수거 업무도 함께 처리하는 것이 이동 거리를 줄이는 방법이다. 즉, 가장 먼 곳의 작업을 우선적으로 해결하는 그리디방식이 적절하다.
2. 배달과 수거는 같은 이동 경로 안에서 이루어진다. 트럭이 한 번 왕복할 때, 갈 때는 최대 cap만큼의 배달 물건을 싣고 갈 수 있고, 올 때는 최대 cap만큼의 수거 물건을 싣고 올 수 있다. 즉, 한 번의 왕복 이동(거리 x 2)으로 배달 cap개와 수거 cap개를 처리할 수 있는 잠재력이 생긴다.

2. 접근 방법

단순히 시뮬레이션을 돌리기에는 생각해야 할 변수가 많다. 하지만 가장 먼 집부터 생각하면 문제는 매우 단순해진다.

각 위치(i)에서 처리해야 할 배달 양(deliveries[i])과 수거 양(pickups[i])을 누적해 나가면서, 적재 용량이 초과될 때마다 트럭을 배차(왕복 이동)한다고 생각하면 된다.

구체적인 알고리즘 순서는 다음과 같다.

1. 배열을 가장 먼 집부터 순회한다.
2. 현재 집에서 처리해야 할 배달 개수와 수거 개수를 각각 변수(d_val, p_val)에 더한다.
3. 만약 d_val이나 p_val 중 하나라도 양수라면(즉, 처리해야 할 물량이 남아 있다면), 트럭이 해당 위치까지 이동해야 함을 의미한다.
4. 트럭이 한 번 이동할 때마다 cap만큼의 배달과 수거를 처리할 수 있다. 따라서 d_val과 p_val이 모두 0 이하가 될 때까지 트럭을 반복해서 보낸다.
   • 트럭 1회 왕복 시: answer += (현재 거리 + 1) * 2
   • 처리 물량 차감: d_val -= cap, p_val -= cap
5. 여기서 d_val이나 p_val이 음수가 되는 경우가 발생한다. 이는 이번 이동으로 해당 집의 물량을 다 처리하고도, 트럭에 공간이 남았다는 의미다. 이 남은 공간(음수 값)은 더 가까운 집의 물량을 처리할 때 사용된다. (잉여 용량의 이월)

3. 예시를 통한 검증

cap = 4, 집이 5개일 때 가장 먼 5번째 집부터 본다고 가정하자.

• 5번째 집: 배달 2, 수거 0
  • 누적 배달(d_val): 2
  • 누적 수거(p_val): 0
  • d_val이 양수이므로 트럭 이동 필요.
  • 거리 추가: 5 * 2 = 10
  • 물량 처리: d_val -= 4 (결과 -2), p_val -= 4 (결과 -4)
  • 해석: 5번째 집을 위해 트럭이 갔다 오면서 배달 2개를 처리했다. 배달 용량 2개, 수거 용량 4개가 남은 상태(음수 값)로 더 가까운 집으로 넘어간다.
• 4번째 집: 배달 1, 수거 4
  • 누적 배달(d_val): -2 + 1 = -1
  • 누적 수거(p_val): -4 + 4 = 0
  • 둘 다 0 이하이므로 추가 이동 불필요. 5번째 집을 다녀오는 길에 처리가 가능하다.

이 방식을 0번째 집까지 반복하면 최소 이동 거리가 구해진다.

4. 정답 코드 

 

def solution(cap, n, deliveries, pickups):
    answer = 0
    
    # 현재 배달/수거해야 할 누적 택배 개수
    d_val = 0
    p_val = 0
    
    # 가장 먼 집부터 거꾸로 확인 (n-1 부터 0까지)
    for i in range(n - 1, -1, -1):
        d_val += deliveries[i]
        p_val += pickups[i]
        
        # 배달하거나 수거할 택배가 남아있다면 트럭을 배차해야 함
        while d_val > 0 or p_val > 0:
            d_val -= cap
            p_val -= cap
            
            # 왕복 거리를 더해줌 (i는 인덱스이므로 거리는 i+1)
            answer += (i + 1) * 2
            
    return answer

5. 코드 설명 및 분석

• range(n - 1, -1, -1): 가장 먼 집부터 탐색하기 위해 역순으로 반복문을 수행한다.
• d_val, p_val: 각 시점에서 처리해야 할 배달 및 수거의 '잔여량'을 나타낸다.
• d_val += deliveries[i]: 현재 집에 필요한 배달량을 더한다.
• while d_val > 0 or p_val > 0: 현재 위치(혹은 그보다 먼 위치들에서 넘어온)에서 처리해야 할 잔여량이 양수라면, 트럭이 추가로 와야 한다는 뜻이다.
  • d_val -= cap, p_val -= cap: 트럭이 한 번 올 때 cap만큼 배달하고 cap만큼 수거할 수 있으므로, 각각 cap을 뺀다.
  • answer += (i + 1) * 2: 해당 위치(i+1)까지 왕복 이동한 거리를 더한다.
• 음수 값의 의미: while문을 탈출했을 때 d_val이나 p_val이 음수라면, 이는 트럭에 빈 공간이 남았다는 뜻이다. 이 빈 공간은 다음 반복(더 가까운 집)에서 deliveries[i-1]을 더할 때 상쇄되어, 가까운 집을 방문하지 않고도 물량을 처리하는 효과를 낸다.

이 로직은 배열을 한 번만 순회하므로 시간 복잡도는 O(n)이며, n이 최대 100,000인 경우에도 충분히 효율적으로 동작한다. 복잡한 시뮬레이션 없이 숫자(용량)의 덧셈과 뺄셈만으로 문제를 해결하는 깔끔한 방식이다.