[프로그래머스/python] Level 2 : 택배 배달과 수거하기

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

프로그래머스

그리디 문제이다.

예제 풀이를 따라 코드를 작성하면, 아마 시간초과가 발생할 것이다. n이 최대 100,000까지므로 n^2의 시간복잡도로는 문제를 풀 수 없다.

 

우선, 한번에 최대한 멀리가서 멀리 있는 곳들의 작업을 먼저 끝내야지 이동횟수를 최소한으로 만들 수 있으므로 입력받은 배열들을 역순으로 뒤집어준다. 가장 먼 곳부터 탐색을 시작하는데, 배달해야 하거나 픽업해와야 할 것들이 하나라도 있으면 그곳으로 이동한다!

어차피 한번 가면 다시 물류창고로 되돌아와야 하므로 정답에는 거리 x 2를 더해준다.

 

이때 각 위치의 배달/픽업 값들에서 cap값을 빼준다. 이 연산의 결과들이 모두 음수라면 해당 위치의 배달/픽업 값이 한번에 실어 나를 수 있는 용량(=cap)보다 적은 것이므로, 오가는 길에 겸사겸사 추가적으로 배달/픽업이 가능하다는 의미이다!

때문에 have_to_deli, have_to_pick 값이 양수가 되기 전까진 이동이 필요 없고, 이 두 값 중 하나라도 양수가 될 때만 해당 위치로 이동해주면 된다.

def solution(cap, n, deliveries, pickups):
    deliveries = deliveries[::-1]
    pickups = pickups[::-1]
    answer = 0

    have_to_deli = 0
    have_to_pick = 0

    for i in range(n):
        have_to_deli += deliveries[i]
        have_to_pick += pickups[i]

        while have_to_deli > 0 or have_to_pick > 0:
            have_to_deli -= cap
            have_to_pick -= cap
            answer += (n - i) * 2

    return answer