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

https://school.programmers.co.kr/learn/courses/30/lessons/150369

프로그래머스

 

2023 카카오 코테 문제라고 한다.

 

유형들을 보니 알고리즘 적용은 기초적인 수준을 요구하되 아이디어나 DP 적인 해결방법을 요구하는 문제가 출제되는게 대세같다.

 

문제 설명

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

풀이

import Foundation

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
}