프로그래머스 - 택배 배달과 수거하기

문제

def solution(cap, n, deliveries, pickups):
    suffixSumD = [delivery for delivery in deliveries]
    suffixSumP = [pickup for pickup in pickups]
    
    for idx in range(n-2, -1, -1):
        suffixSumD[idx] = suffixSumD[idx+1] + suffixSumD[idx]
        suffixSumP[idx] = suffixSumP[idx+1] + suffixSumP[idx]
    
    sumCap = 0
    answer = 0
    for idx in range(n-1, -1, -1):
        target = max(suffixSumD[idx], suffixSumP[idx])
        if target == 0: break
        if target > sumCap:
            visitFrequency = (target - sumCap) // cap + (1 if target % cap else 0)
            answer += (idx+1) * visitFrequency
            sumCap += visitFrequency * cap
    
    return answer * 2

사실 크게 어렵지 않은 문제라 생각했지만 정답에 가까운 답을 도출하는데는 꽤 많은 시간이 걸렸고 어려운 문제는 아니지만 나의 풀이법을 소개하고 싶어 포스팅하게 되었습니다.

수 많은 시행착오

처음에는 모든 택배상자를 배달하고 픽업하는 한번의 사이클을 매번 시행하는 방식으로 접근하였습니다. 하지만 당연하게도 시간초과였고 더 나은 방법을 찾았습니다.
그리고 두번째는 배달하고 픽업하는 한 번의 사이클을 이분탐색으로 구현하여 조금더 시간을 줄였지만 여전히 부족했고 더 나은 방법을 찾아야했습니다.
그래서 찾게된 방법이 다음과 같습니다. 이 문제에 대해서 자세히 고민하지 않으면 이해가 되지 않을 수 있으니 설명을 듣고 이해가 되지 않는다고 포기하지 말고 문제를 다시 한번 보고 생각해보시길 추천합니다.

문제의 포인트

문제의 포인트는 여러가지인데 이를 소개하자면

1. 배달과 픽업은 독립적으로 보는게 문제 풀기에 쉽다.
   언뜻 보면 매우 연관이 있지만 사실 둘 사이에는 큰 연관이 없습니다.
2. 한번의 이동으로 가야하는 최대 지점을 구하는 방식은 뒤에서 부터 보는것 입니다.

문제 풀이

그럼 지금부터 코드를 보면서 자세히 한번 포인트를 가지고 설명해보겠습니다.

suffixSumD = [delivery for delivery in deliveries]
suffixSumP = [pickup for pickup in pickups]

이것이 문제의 가장 핵심인 sufixSum배열입니다. 트럭 한번의 이동으로 픽업 혹은 배달 가능한 양은 정해져있습니다. 그럼 우리는 surfixSum배열을 통해 특정 index의 모든 수량을 처리하려면 몇 번의 트럭이동이 필요한지 계산할 수 있습니다.

1, 0, 3, 1, 2 의 배열이 있고
7, 6, 6, 3, 2 은 위의 배열의 suffixSum배열입니다.

한 번의 이동에 4의 수량을 픽업 혹은 배달할 수 있다고 생각하면 뒤에서 부터 보면 2와 3까지는 한번에 이동가능하고 6이 되면 이제 한번이 아닌 2번의 이동으로 해결할 수 있으며 두번의 이동으로는 8의 수량이 처리가능해지니 더 이상의 이동이 필요하지 않게 됩니다.
그럼 4번 인덱스까지 이동하고 2번 인덱스까지 2번 이동하면 모든 수량이 처리되기 때문에 (5 + 3) * 2 해서 16이 답이 됩니다.

그럼 아래의 코드를 통해 답을 도출하는 과정을 보겠습니다.

sumCap = 0  # 트럭의 총 처리가능한 수량 -> 트럭의 이동 횟수에 따라 달라지는 변수 입니다.
answer = 0
for idx in range(n-1, -1, -1):
    target = max(suffixSumD[idx], suffixSumP[idx])
    # 픽업과 택배 중 더 큰 값을 기준으로만 처리하면 됩니다.
    # 그 이유는 픽업과 택배는 독립적이기 때문이죠.
    # 이 부분이 이해가 되지 않는다면 문제를 다시 한번 보고 오시면 이해가 되실겁니다.
    if target == 0: break
    # target이 0이다. 즉, 더이상 처리할 수량이 남아있지 않다는것 반복문을 종료!
  
    # target이 sumCap보다 작거나 같은 경우는 이미 트럭의 이동에 의해 
    # 모든 물량이 처리되는 경우이기 때문에 더 이상의 트럭의 이동이 필요하지 않습니다.
    if target > sumCap:
    	# 특정 index에 트럭이 몇 번 왔다갔다 해야 하나를 계산한 변수입니다.
       	# while 문으로 처리할 수도 있지만 조금 더 시간을 아끼기 위해 수학적으로 해결하였습니다.
   	    visitFrequency = (target - sumCap) // cap + (1 if target % cap else 0)
        answer += (idx+1) * visitFrequency
        sumCap += visitFrequency * cap

return answer * 2

혹시라도 이해가 되지 않는 부분이 있다면 댓글로 달아주세요. 최대한 도와드리겠습니다.