문제 링크

문제 풀이 아이디어

Greedy!

제가 생각하는 이번 문제의 핵심은 “각 집에 배달 및 수거할 때, 원하는 개수만큼 택배를 배달 및 수거할 수 있습니다.”라는 표현입니다. 문제에서도 볼드 처리가 되어 있는데요. 이 말은 즉 “같은 집에 1번 이상 방문해서 배달 혹은 픽업을 할 수 있다”는 뜻입니다.

따라서 극단적으로 말하면 일직선에 위치한 집들에 가면서는 “배달만”하고 오면서는 “픽업만” 할 수 있다는 뜻입니다. 즉 트럭에 배달할 짐을 가득 채워가도 돌아올 때 가득 채워서 픽업을 해올 수 있다는 점입니다. 즉 그리디 알고리즘을 사용할 때 “중간에 픽업할 자리가 부족하지 않을까?”라는 걱정을 하지 않아도 된다는 점입니다.

따라서 가장 먼 집부터 배달합니다. 가장 먼 집을 2번 이상 방문하는 것은 비효율적이기 때문입니다. 가장 먼 집부터 방문과 픽업을 하면서 점점 이동거리를 줄여야 합니다.

Stack

한번 배달을 떠날 때 트럭에 최대한 많은 짐을 싣고 떠나고 올 때 최대한 많은 짐을 가지고 돌아와야 합니다. 그리고 먼집 부터 계산을 해야합니다. 이럴 때 Stack을 활용하면 편합니다.

배달과 픽업을 하면서 Stack을 활용하여 이미 배달한 집은 pop하면 됩니다. 그 집에 한번에 배달을 다 하지 못할 때는 pop하지 않고 싣을 수 있는 짐의 갯수만큼만 빼주면 됩니다.

거리 계산

거리는 Stack의 길이를 활용하면 됩니다. Stack의 첫번째 원소는 거리가 1인 집을 의미합니다. 따라서 Stack의 길이가 n일 때 마지막 집은 거리가 n인 집입니다. 여기서 주의할 점은 배달 (혹은 픽업)할 짐이 0인 집은 빼주어야 한다는 점입니다. 따라서 처음에 deliveries와 pickups 배열에서 맨 뒤 원소가 0인 경우는 모두 제거해주고 문제를 풉니다.

코드

처음에 Greedy를 생각하기는 했는데 “각 집에 배달 및 수거할 때, 원하는 개수만큼 택배를 배달 및 수거할 수 있습니다.”을 뒤늦게 발견하는 바람에 좀 고생을 했네요. 다 풀고나면 아주 전형적인 그리디 문제임을 알 수 있습니다.

func solution(_ cap:Int, _ n:Int, _ deliveries:[Int], _ pickups:[Int]) -> Int64 {
    
    var deliveries = deliveries
    var pickups = pickups
    
    // 배달이 0인 마지막 집은 제거
    while let last = deliveries.last, last == 0 {
        _ = deliveries.popLast()
    }
    
    // 픽업이 0인 마지막 집은 제거
    while let last = pickups.last, last == 0 {
        _ = pickups.popLast()
    }
    
    var ans = 0
    
    // 배달과 픽업이 모두 끝나면 종료
    while !(deliveries.isEmpty && pickups.isEmpty) {
        
        // 이번 배달에서 나갈 거리 (= 배달 or 픽업 거리가 있는 가장 먼 집의 거리)
            // 왕복이므로 * 2
        ans += max(deliveries.count, pickups.count) * 2
        
        var d = 0
        var p = 0
        
        // 최대한 멀리 & 많이 배달 -> 마지막 집에 배달할 물건부터 계산
        while !deliveries.isEmpty {
            // 현재 갈 집에 배달할 물건을 모두 싣을 수 있는 경우
            if d + deliveries.last! <= cap {
                d += deliveries.popLast()!
            } else { // 다 싣을 수 없는 경우
                deliveries[deliveries.count - 1] -= cap - d //싣을 수 있는 만큼만 싣는다
                break
            }
        }
        
        // 최대한 멀리 & 많이 픽업 -> 마지막 집에 픽업할 물건부터 계산
        while !pickups.isEmpty {
            // 현재 갈 집에 픽업할 물건을 모두 가지고 돌아올 수 있는 경우
            if p + pickups.last! <= cap {
                p += pickups.popLast()!
            } else { // 다 가지고 돌아올 수 없는 경우
                pickups[pickups.count - 1] -= cap - p // 가져올 수 있는 만큼만 싣는다
                break
            }
        }
    }
    
    return Int64(ans)
}