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

문제

 

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

프로그래머스

 

 

풀이

 

처음에 풀었을 때는 반복문의 중첩으로 배열을 전부 탐색해서 해결했다. 그래서 세 개의 케이스에서 시간초과가 났따. 10^5이므로 최악의 경우 충분히 시간초과가 나올 수 있는 크기였다.

 

그래서 한 번의 반복문을 통해 해결하려고 해보았따.

 

해결하기까지는 오래걸렸지만 막상 해결하고 나니 충분히 더 빨리 풀 수 있는 문제였다. 

우선, 가장 마지막부터 처리하는 것이 가장 빠른 방법인 것을 알아야한다.

 

일단, del과 pick 두 개의 변수를 만들었다. 각각 배달한 물건과 수거하는 물건의 여유분이라고 생각하면 된다. 이게 무슨말인지 아래의 설명을 보면 이해가 될 것이다.

 

가장 먼 곳부터 처리하는 것이 가장 빠른 방법이므로 n - 1번째 인덱스의 원소부터 확인한다. del과 pick의 초기값은 0이다. 이제 deliveries와 pickups의 가장 마지막 원소를 확인해본다.

deliveries의 마지막 원소가 2이고 pickups의 마지막 원소가 0인 경우를 생각해보자. del은 배달할 물건의 여유분이라고 하였다. deliveries[i]가 2라는 것은 마지막 집에 배달해야할 물건이 2개라는 것이다. 그래서 여유분에서 deliveries[i]를 빼면 마지막 집을 한 번 방문했다고 볼 수 있따. 마찬가지로 pickups에서도 동일하게 적용된다. 

각각 빼고나면 del과 pick의 값은 -2와 0이 될 것이다. 왜냐하면 여유분이 없는 초기상태에서 마지막집에 2개의 택배를 배달했기때문이다. 여유분은 음수가 되면 안된다. 여유분이 음수라는 것은 해당 집에 반드시 택배를 들고 가야한다는 얘기가 된다. 만약 각각 값을 빼고 나서도 두 값이 모두 0보다 크면 이전에 더 먼 곳을 다녀가면서 채울 수 있었다는 얘기이므로 방문할 필요가 없다는 의미이다.

 

아무튼 다시 이전 예시를 보면 del이 음수가 된다. 이 말은 반드시 i번째 집에 방문해야한다는 의미이다. 이때, 최대로 들고 갈 수 있는 택배의 개수는 cap이다. del이 음수가 되지 않기 위해서 더해야하는 cap의 배수의 최소값은 4이다.(예시의 cap값은 4) 

즉 i번째(지금은 마지막) 집은 한 번만 왔다가면된다는 의미이다. 그래서 result에는 i번째 집까지의 거리인 i + 1의 두 배에 temp값을 곱한 값을 더해준다. 여기서의 temp는 방문해야하는 횟수를 의미한다. 지금은 한 번만 방문해도 양수가 되기때문에 temp가 1인 것이다.

배달을 하러 가면서 수거를 따로 처리할 수 있다. 그렇기 때문에 del과 pick에 모두 4를 더해준 뒤에 다음으로 먼 집을 방문하면 된다. 

 

다음으로 먼 집은 1개를 배달해야하고, 4개를 수거해야한다. 우리는 마지막 집의 택배를 처리하면서 생긴 여유분이 있다. del은 2, pick은 4의 값을 가지고 있을 것이다. 그래서 del에선 1을, pick에선 4를 빼면 둘 다 0 이상이다. 그러므로 이 집은 방문할 필요가 없다는 얘기이다. 

이전 집을 방문할때 현재의 집을 지나칠텐데 최대로 cap만큼을 운반할 수 있기 때문에 그만큼의 여유분으로 미리 처리해둘 수 있는 것이다. 

 

이런식으로 처리하면 한 번의 반복문으로 결과를 구할 수 있다.

import Foundation

func solution(_ cap:Int, _ n:Int, _ deliveries:[Int], _ pickups:[Int]) -> Int64 {
    
    var result: Int64 = 0
    var del = 0
    var pick = 0
    
    for i in stride(from: n - 1, through: 0, by: -1) {
        del -= deliveries[i]
        pick -= pickups[i]
        if del >= 0 && pick >= 0 {
            continue
        }
        let minValue = min(pick,del)
        var temp = 0
        if abs(minValue) % cap == 0 {
            temp = abs(minValue) / cap
        } else {
            temp = (abs(minValue) / cap) + 1
        }
        del += cap * temp
        pick += cap * temp
        result += Int64((i+1) * 2 * temp)
    }
    return result
}

설명을 나만 이해할 것 같음.

 

_____________________________________________________________________________________________________

 

 

은근히 오래걸렸다. 그리고 stride는 to와 through일때 차이가 있으므로 기억하기.