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

👆문제풀러 가기👆

문제 설명

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

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

---

풀이 [ 메모리: 24mb, 최대시간: 119.46ms ] 

func solution(_ cap:Int, _ n:Int, _ deliveries:[Int], _ pickups:[Int]) -> Int64 {
    // cap = 최대 수용가능한 택배상자
    // n = 집 갯수
    // deliveries = 집마다 배달해야할 물건들
    // pickups = 집마다 가져와야할 빈상자들

    var deliveries = deliveries
    var pickups = pickups
    var d = 0
    var p = 0
    var distance = 0
    var i = n-1

    while i >= 0 {
        if deliveries[i] == 0 && pickups[i] == 0 {
            i -= 1
            continue
        }

        if d < deliveries[i] || p < pickups[i] {
            d += cap
            p += cap
            distance += (i+1)
            continue
        }

        d -= deliveries[i]
        p -= pickups[i]
        i -= 1
    }

    return Int64(distance) * 2
}

시간초과로 고통받았던 문제..

함께 스터디하는 분이 어떻게 풀었는지를 듣고, 다음날 설명기반으로 코드를 짜봤다.

 

풀이를 위한 표

예제에서 보다시피, 

1. 가장 멀리 있는 곳에서부터 배송을 해야 가장 효율적이다
2. 택배기사는 배송할 물건이 있거나 회수할 박스가 있는 가장 멀리있는 곳부터 방문해야한다.
3. 만약 배송할 물건이 없거나 회수할 박스가 없는 곳이면 방문하지 않아야 한다.
4. 택배기사는 최대 수용량을 초과하면 택배회사에 다녀와야 한다.

풀이 설명

이렇게 생각을 하고, 자연스럽게 반복문을 이용해 택배기사가 회사로 복귀하는 로직을 생각하게 된다.

하지만 굳이 회사에 복귀할 필요는 없다. (= 회사에 다녀왔다고 가정을 하면 된다.)

 

임의로 d,p 변수를 만들어 임의 배송 및 회수 후 남은 물품 수를 확인한다.

남은 물품의 수가 택배기사가 갖고 있을 물품의 수 또는 수용량을 초과하게 된다면, 

회사에 다녀와 물건을 챙겨오고, 박스를 반납했다고 생각하자 (+ cap)

회사에 다녀온 시점(Index)의 합 * 2(왕복)이 정답으로 도출된다.

 

이와같은 과정으로 풀었을 때 반복문이 현저히 줄어들어 시간초과의 늪에서 벗어날 수 있다..!

 

기존풀이 [ 16, 17, 19, 20 테스트케이스 시간초과 ]

func solution2(_ cap:Int, _ n:Int, _ deliveries:[Int], _ pickups:[Int]) -> Int64 {
    var deliveries = [0] + deliveries
    var pickups = [0] + pickups
    var n = n
    var distance = 0

    while n > 0 {
        var (deliveryBoxes, emptyBoxes) = (cap, 0)
        var isFirst = true

        for i in stride(from: n, through: 0, by: -1) {
            if deliveries[i] != 0 || pickups[i] != 0 {
                n = i
                break
            }
            n = 0
        }

        if isFirst {
            isFirst = false
            distance += n * 2
        }

        for i in stride(from: n, through: 0, by: -1) {
            if deliveryBoxes <= 0 && emptyBoxes >= cap { break }

            // print("\(i)번째")
            if deliveryBoxes > 0  {
                deliveryBoxes -= deliveries[i]
                deliveries[i] = (deliveryBoxes >= 0) ? 0 : (-deliveryBoxes)
            }

            if emptyBoxes < cap {
                emptyBoxes += pickups[i]
                pickups[i] = (emptyBoxes <= cap) ? 0 : (emptyBoxes - cap)
            }
        }
    }
    return Int64(distance)
}

스터디를 하기 잘했다고 생각이 들었던 문제이다.

만약 평소처럼 혼자 공부하고 다른 사람의 풀이를 봤다면,

제대로 이해하지 못했거나 그정도 수준에 머물렀을 것 같은데,

깔끔한 설명으로 어떻게 푸는지를 명확히 알 수 있었다.