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

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

프로그래머스

1. 문제 접근

문제를 보고 그리디로 접근해야겠다. 라는 느낌은 왔다.

하지만 어떻게 그리디를 구현하냐가 문제였다.

가장 먼 곳부터 해결해야 하는 것은 알겠는데 출발 할 때에 물류창고에서 택배차 설정을 어떻게 해야하지?

• 너무 많이 가져가면 가장 먼 곳의 빈 택배박스를 회수 못할 경우가 생긴다. -> 한 번 더 왕복해야 한다.
• 너무 적게 가져가면 택배를 건네주기 위해서 다시 왕복해야 한다.

이게 문제였다. 

하지만 문제 접근이 잘못되었다.

가장 먼 곳의 상황을 모를 때에는 위 고민이 맞으나 우리는 가장 먼 곳의 택배상황을 알고 있으니 거꾸로 접근하면 된다.

2. 문제 풀이

import Foundation

func solution(_ cap:Int, _ n:Int, _ deliveries:[Int], _ pickups:[Int]) -> Int {
    var sopo = deliveries.reversed().map{$0}
    var pick = pickups.reversed().map{$0}
    var distance = 0
    var d = 0
    var p = 0
    
    for i in 0 ..< n {
        d += sopo[i]
        p += pick[i]
        
        while d > 0 || p > 0 {
            d -= cap
            p -= cap
            
            distance += (n - i) * 2
        }
    }
    
    return distance
}

d와 p가 분명 음수가 발생한 경우가 생길 것이다. 여기서 음수가 갖는 의미는 크다.

음수가 갖는 의미에 대해서 생각해보자.

분명 가장 먼 곳의 택배 배송만을 혹은 빈 택배 박스를 회수만을 위해서 가장 먼 곳을 가야하는 경우가 생길 것이다. 문제 예시처럼 말이다.

가장 먼 곳만 찍고 돌아오는 것은 매우 비효율적인 일이다. 그러므로 반드시 돌아오는 길에 다른 곳의 택배를 배송하든, 빈 택배를 회수해야한다. 

그리고 가장 먼 곳을 제외하고 다른 택배 배송가능한 여력과, 빈 택배를 회수할 여력을 음수로 표시하는 것이다.

3. 문제 후기

문제 접근, 그리디를 떠올리기는 쉬운 것 같았다. 하지만 어떻게 그리디를 구현하냐가 문제였다. Level 2는 아닌 것 같은 느낌이다.

한 Level 3 ??