파이썬) 택배 배달과 수거하기

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

프로그래머스

 

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(len(deliveries)):
        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

이 문제는 내가 실패한 문제이다.

길이가 최대 10만인 점으로 보아 n^2 즉, 이중 for문으로 풀 수 없다는 점을 인지했지만 어떻게 최소한의 거리를 측정할지를 생각해내지 못했다.

그래서 다른 분의 답안을 참조했다.

위 코드는 다음과 같다.

우선 가장 먼 거리를 먼저 다녀와야 동선의 낭비가 없다. 그래서 deliveries와 pickups의 리스트를 뒤집어 주었다.

그 다음 have_to_deli와 have_to_pick 을 선언해주었다. 이것은 deliveries리스트를 돌며 deliveries[i]가 가진 배달해야 할 택배 수와 수거해야 할 택배의 수를 집어 넣는다.

이들의 수를 계산해본 결과( have_to_deli+= deliveries[i]
        have_to_pick += pickups[i]) 음수라면 한 번에 나를 수 있는 용량보다 적은 것이므로 오가는 길에 추가적인 배달 또는 수거를 할 수 있다는 의미이다.