Post

[프로그래머스] 택배 배달과 수거하기 (Go, Python)

Posted
By Kang Minsu 19 min read

문제

문제 설명

택배 배달과 수거하기1

당신은 일렬로 나열된 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/00/33/01/42/0물류창고에서 택배 3개를 트럭에 실어 출발합니다.
남은 배달/수거1/00/33/00/40/0물류창고에서 5번째 집까지 이동하면서(거리 5) 4번째 집에 택배 1개를 배달하고, 5번째 집에 택배 2개를 배달합니다.
남은 배달/수거1/00/33/00/00/05번째 집에서 물류창고까지 이동하면서(거리 5) 4번째 집에서 빈 택배 상자 4개를 수거한 후, 수거한 빈 택배 상자를 물류창고에 내리고 택배 4개를 트럭에 싣습니다.
남은 배달/수거0/00/30/00/00/0물류창고에서 3번째 집까지 이동하면서(거리 3) 1번째 집에 택배 1개를 배달하고, 3번째 집에 택배 3개를 배달합니다.
남은 배달/수거0/00/00/00/00/03번째 집에서 물류창고까지 이동하면서(거리 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/00/22/00/11/00/22/0물류창고에서 택배 2개를 트럭에 실어 출발합니다.
남은 배달/수거1/00/22/00/11/00/20/0물류창고에서 7번째 집까지 이동하면서(거리 7) 7번째 집에 택배 2개를 배달합니다.
남은 배달/수거1/00/22/00/11/00/00/07번째 집에서 물류창고까지 이동하면서(거리 7) 6번째 집에서 빈 택배 상자 2개를 수거한 후, 수거한 빈 택배 상자를 물류창고에 내리고 택배 2개를 트럭에 싣습니다.
남은 배달/수거1/00/21/00/10/00/00/0물류창고에서 5번째 집까지 이동하면서(거리 5) 3번째 집에 택배 1개를 배달하고, 5번째 집에 택배 1개를 배달합니다.
남은 배달/수거1/00/11/00/00/00/00/05번째 집에서 물류창고까지 이동하면서(거리 5) 4번째 집에서 빈 택배 상자 1개를 수거하고 2번째 집에서 빈 택배 상자 1개를 수거한 후, 수거한 빈 택배 상자를 물류창고에 내리고 택배 2개를 트럭에 싣습니다.
남은 배달/수거0/00/10/00/00/00/00/0물류창고에서 3번째 집까지 이동하면서(거리 3) 1번째 집에 택배 1개를 배달하고, 3번째 집에 택배 1개를 배달합니다.
남은 배달/수거0/00/00/00/00/00/00/03번째 집에서 물류창고까지 이동하면서(거리 3) 2번째 집에서 빈 택배 상자 1개를 수거한 후, 수거한 빈 택배 상자를 물류창고에 내립니다.

30(=7+7+5+5+3+3)의 거리를 이동하면서 모든 배달 및 수거를 마쳤습니다. 같은 거리로 모든 배달 및 수거를 마치는 다른 방법이 있지만, 이보다 짧은 거리로 모든 배달 및 수거를 마치는 방법은 없습니다. 따라서, 30을 return 하면 됩니다.

풀이

Go

구현

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51

func solution(cap int, n int, deliveries []int, pickups []int) int64 {
    var answer int64
    
    d := []int{}
    p := []int{}
    for i:=n-1; i>=0; i-- {
        if deliveries[i] != 0 {
            d = append(d, i)
        }
        if pickups[i] != 0 {
            p = append(p, i)
        }
    }
    
    for len(d) != 0 || len(p) != 0 {
        max := -1
        if len(d) > 0 && d[0] > max {
            max = d[0]
        }
        if len(p) > 0 && p[0] > max {
            max = p[0]
        }
        answer += (int64(max) + 1) * 2
        
        delivery, pickup := 0, 0
        for len(d) > 0 {
            now := d[0]
            if delivery + deliveries[now] > cap {
                deliveries[now] -= cap - delivery
                break
            } else {
                delivery += deliveries[now]
                deliveries[now] = 0
                d = d[1:]
            }
        }
        for len(p) > 0 {
            now := p[0]
            if pickup + pickups[now] > cap {
                pickups[now] -= cap - pickup
                break
            } else {
                pickup += pickups[now]
                pickups[now] = 0
                p = p[1:]
            }
        }
    }
    
    return answer
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

테스트 1 〉	통과 (0.00ms, 4.19MB)
테스트 2 〉	통과 (0.00ms, 4.23MB)
테스트 3 〉	통과 (0.00ms, 3.73MB)
테스트 4 〉	통과 (0.00ms, 3.56MB)
테스트 5 〉	통과 (0.01ms, 3.57MB)
테스트 6 〉	통과 (0.01ms, 4.23MB)
테스트 7 〉	통과 (0.05ms, 4.23MB)
테스트 8 〉	통과 (0.05ms, 3.56MB)
테스트 9 〉	통과 (0.19ms, 4.16MB)
테스트 10 〉	통과 (0.28ms, 4.21MB)
테스트 11 〉	통과 (0.16ms, 4.11MB)
테스트 12 〉	통과 (0.12ms, 3.55MB)
테스트 13 〉	통과 (0.14ms, 4.27MB)
테스트 14 〉	통과 (0.14ms, 4.22MB)
테스트 15 〉	통과 (4.48ms, 12.5MB)
테스트 16 〉	통과 (13.43ms, 14.2MB)
테스트 17 〉	통과 (5.63ms, 13.5MB)
테스트 18 〉	통과 (7.44ms, 15.9MB)
테스트 19 〉	통과 (4.56ms, 12.8MB)
테스트 20 〉	통과 (4.68ms, 13.9MB)
  1. 방문해야 하는 집들의 인덱스를 역순으로 Array에 넣는다.
  2. 배송, 픽업 Array에서 첫번째 값들을 꺼내 더 큰 값을 찾으면 해당 회차에서 방문해야 할 가장 먼 집의 위치이다.
  3. 배송, 픽업 각각의 거리에서 값을 누적해서 cap 이하를 만족할 때까지 나아간다.
    • 특정 거리까지의 합이 cap 보다 작을경우 해당 값을 Array에서 제거한다.

누적합

1
2
3
4
5
6
7
8
9
10
11
12
13
14

func solution(cap int, n int, deliveries []int, pickups []int) int64 {
    var answer int64
    d, p := 0, 0
    for i:=n-1; i>=0; i-- {
        d -= deliveries[i]
        p -= pickups[i]
        for d < 0 || p < 0 {
	        answer += (int64(i) + 1) * 2
            d += cap
            p += cap
        }
    }
    return answer
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

테스트 1 〉	통과 (0.00ms, 4.2MB)
테스트 2 〉	통과 (0.00ms, 3.54MB)
테스트 3 〉	통과 (0.00ms, 3.72MB)
테스트 4 〉	통과 (0.00ms, 4.2MB)
테스트 5 〉	통과 (0.00ms, 3.54MB)
테스트 6 〉	통과 (0.00ms, 4.23MB)
테스트 7 〉	통과 (0.00ms, 3.54MB)
테스트 8 〉	통과 (0.01ms, 4.2MB)
테스트 9 〉	통과 (0.03ms, 4.2MB)
테스트 10 〉	통과 (0.03ms, 4.3MB)
테스트 11 〉	통과 (0.02ms, 4.12MB)
테스트 12 〉	통과 (0.02ms, 3.54MB)
테스트 13 〉	통과 (0.01ms, 3.54MB)
테스트 14 〉	통과 (0.01ms, 3.54MB)
테스트 15 〉	통과 (0.21ms, 8.07MB)
테스트 16 〉	통과 (2.60ms, 8.07MB)
테스트 17 〉	통과 (0.78ms, 8.13MB)
테스트 18 〉	통과 (0.50ms, 7.98MB)
테스트 19 〉	통과 (0.38ms, 8.19MB)
테스트 20 〉	통과 (0.40ms, 7.95MB)
  1. n-1 번째 인덱스부터 거꾸로 내려오며 상자 갯수를 더해준다.
  2. 배송, 픽업 중 상자의 갯수가 0을 초과하면 거리를 계산해서 더해준다.
  3. 배송, 픽업 상자의 갯수에서 cap 만큼 빼준다.

Python

구현

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

def solution(cap, n, deliveries, pickups):
    answer = 0
    
    d, p = [], []
    for i in range(n-1, -1, -1):
        if deliveries[i]:
            d.append(i)
        if pickups[i]:
            p.append(i)
            
    while d or p:
        max_ = -1
        if d and d[0] > max_:
            max_ = d[0]
        if p and p[0] > max_:
            max_ = p[0]
            
        answer += (max_ + 1) * 2
        
        delivery, pickup = 0, 0
        while d:
            now = d[0]
            if delivery + deliveries[now] > cap:
                deliveries[now] -= cap - delivery
                break
            else:
                delivery += deliveries[now]
                deliveries[now] = 0
                d.pop(0)  # d = d[1:] 은 실패
        
        while p:
            now = p[0]
            if pickup + pickups[now] > cap:
                pickups[now] -= cap - pickup
                break
            else:
                pickup += pickups[now]
                pickups[now] = 0
                p.pop(0)
                
    return answer

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

테스트 1 〉	통과 (0.02ms, 10.1MB)
테스트 2 〉	통과 (0.01ms, 10.2MB)
테스트 3 〉	통과 (0.03ms, 10.2MB)
테스트 4 〉	통과 (0.02ms, 10.3MB)
테스트 5 〉	통과 (0.06ms, 10.3MB)
테스트 6 〉	통과 (0.05ms, 10.2MB)
테스트 7 〉	통과 (1.43ms, 10.2MB)
테스트 8 〉	통과 (2.74ms, 10.3MB)
테스트 9 〉	통과 (12.49ms, 10.4MB)
테스트 10 〉	통과 (10.31ms, 10.2MB)
테스트 11 〉	통과 (6.27ms, 10.2MB)
테스트 12 〉	통과 (4.22ms, 10.2MB)
테스트 13 〉	통과 (4.65ms, 10.4MB)
테스트 14 〉	통과 (4.93ms, 10.3MB)
테스트 15 〉	통과 (410.26ms, 15MB)
테스트 16 〉	통과 (3323.78ms, 16MB)
테스트 17 〉	통과 (1276.27ms, 16.1MB)
테스트 18 〉	통과 (2048.58ms, 16.1MB)
테스트 19 〉	통과 (768.14ms, 15.8MB)
테스트 20 〉	통과 (1362.71ms, 16MB)
  • go로 풀었던 방법과 동일한 풀이 이지만 아슬아슬하게 통과됐다.
  • 방문했던 곳을 제거하는 과정에서 슬라이싱을 하게되면 메모리 카피로인해 시간초과로 실패한다.

누적합

1
2
3
4
5
6
7
8
9
10
11
12

def solution(cap, n, deliveries, pickups):
    answer = 0
    d, p = 0, 0
    for i in range(n - 1, -1, -1):
        d += deliveries[i]
        p += pickups[i]
        while d > 0 or p > 0:
            d -= cap
            p -= cap
            answer += (i + 1) * 2
        
    return answer

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

테스트 1 〉	통과 (0.01ms, 10.1MB)
테스트 2 〉	통과 (0.00ms, 10.2MB)
테스트 3 〉	통과 (0.01ms, 10.4MB)
테스트 4 〉	통과 (0.01ms, 10.2MB)
테스트 5 〉	통과 (0.01ms, 10.2MB)
테스트 6 〉	통과 (0.01ms, 10.2MB)
테스트 7 〉	통과 (0.19ms, 10.1MB)
테스트 8 〉	통과 (0.45ms, 10.2MB)
테스트 9 〉	통과 (2.19ms, 10.3MB)
테스트 10 〉	통과 (2.86ms, 10.4MB)
테스트 11 〉	통과 (0.88ms, 10.4MB)
테스트 12 〉	통과 (0.75ms, 10.3MB)
테스트 13 〉	통과 (1.16ms, 10.4MB)
테스트 14 〉	통과 (1.17ms, 10.3MB)
테스트 15 〉	통과 (16.30ms, 11.6MB)
테스트 16 〉	통과 (580.83ms, 11.7MB)
테스트 17 〉	통과 (50.10ms, 11.6MB)
테스트 18 〉	통과 (22.83ms, 11.5MB)
테스트 19 〉	통과 (20.45ms, 11.7MB)
테스트 20 〉	통과 (37.94ms, 11.4MB)
Algorithm, DP
알고리즘 프로그래머스 go python 누적합 구현
This post is licensed under CC BY 4.0 by the author.