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

문제 정보

• 문제 출처

코딩테스트 연습 | 프로그래머스 스쿨

• 문제 링크

프로그래머스

• 제출 언어: Swift
• 알고리즘 분류:
  • 그리디

문제 설명

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

트럭에 실을 수 있는 재활용 택배 상자의 최대 개수를 나타내는 정수 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
• 트럭의 초기 위치는 물류창고입니다.

---

입출력 예

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

---

문제 풀이

이 문제는 핵심 부분은 한 번 배달을 갔으면 무조건 `물류창고`로 돌아와야 하는 것이다. 

그러므로 배달갈 때와 수거할 때 편도로 거리를 각자 구해주는 것이 아니라 왕복으로 배달가야하는 곳 중 가장 먼 곳을 다녀오면서 배달과 수거를 동시해 수행해주면 된다. 

아래의 블로그를 참고하여 Stack의 Last-In-Last-Out 특징을 이용하여 문제를 풀어나갔다. 

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

처음에 del과 picks 배열 모두 뒤에서부터 해당 배열의 값이 0이면 삭제해 초기화하였다.

이 후, del, picks의 배열이 둘 다 empty가 될 때까지, while문을 돌리면서 최소 거리를 구해주었다.

1. 물류창고에서 출발할 때 마다, 배달가야 하는 집과, 수거해야 하는 집 (각 배열의 길이)중 가장 먼 거리의 두 배만큼 result에 더해주었다.

2. 배달갈 집들을 가장 먼 곳부터 살펴보면서, 트럭에 실을 수 있는 만큼 배달을 해주고, 모두 배달을 해준 집은 0이 되므로 pop해주었다.

3. 배달물을 수거할 집들을 가장 먼 곳부터 살펴보면서, 트럭에 실을 수 있는 만큼 수거하고, 모두 수거한 집도 pop해주었다.

 

한번 왕복할 때마다, 배달과 수거를 수행하고 배열의 값이 0이 되면 pop을 해주므로 배열에는 배달 혹은 수거를 가야되는 집만 남아있게 되어 그 배열의 길이를 비교하여 왕복할 때마다 이동해야 되는 가장 먼 거리를 파악할 수 있다.

import Foundation

func solution(_ cap:Int, _ n:Int, _ deliveries:[Int], _ pickups:[Int]) -> Int64 {
    var result = 0
    var del = deliveries
    var picks = pickups
    // 배열의 뒤에서부터 0인 값 pop
    del.trimZeroSuffix()
    picks.trimZeroSuffix()
    
    while !del.isEmpty || !picks.isEmpty {
        result += max(del.count , picks.count) * 2
        var tempCap = cap
        
        // 배달갈 집들
        while !del.isEmpty {
            if del.last! > tempCap {
                del[del.count - 1] -= tempCap
                break
            } else {
                tempCap -= del[del.count - 1]
                del.removeLast()
            }
        }
        
        // 수거할 집들
        tempCap = cap
        while !picks.isEmpty {
            if picks.last! > tempCap {
                picks[picks.count - 1] -= tempCap
                break
            } else {
                tempCap -= picks[picks.count - 1]
                picks.removeLast()
            }
        }
    }
    return Int64(result)
}

extension Array where Element == Int {
    mutating func trimZeroSuffix() {
        while self.last ?? 1 == 0 {
            self.removeLast()
        }
    }
}