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

1. 개요

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

2. 풀이

def solution(cap, n, deliveries, pickups):
    
    # 물건이 있거나 수거할 택배박스가 있는 위치를 뽑아낸다.
    # 인덱스 0부터 끝까지 체크해도되지만 시간복잡도를 줄이는데 도움이 되기 때문이다.
    ds = [ i for i in range(n) if deliveries[i] ] 
    ps = [ i for i in range(n) if pickups[i] ]
    
    answer = 0
    
    # 수거하거나 물건을 배달해야 한다면 반드시 트럭을 출발시킨다.
    while ds or ps:
        
        # 가장 멀리 있는 장소부터 배달하거나 수거한다.
        # 그렇게 해야만 다음에 트럭을 출발시킬때 가야하는 거리를 줄일수 있으므로 최적화가 된다.
        d, p = ds[-1] if ds else -1, ps[-1] if ps else -1
        
        dCap = pCap = cap
        
        # 수거와 배송중 가장 멀리가는거리
        # 왔다갔다해서 2번이다.
        answer += (max(d, p)+1)*2
        
        # 택배를 먼저 배송시키고
        # 돌아오면서 택배를 수거할수 있기 때문에 
        # 한번 트럭을 출발시킬때마다 cap개의 택배를 배송시키고
        # cap개의 택배를 숙거할수 있다.
        
        # 택배 배송
        while dCap and ds:
            reduced = min(deliveries[ds[-1]], dCap)
            deliveries[ds[-1]] -= reduced
            dCap -= reduced
            
            if deliveries[ds[-1]]:
                break
            ds.pop()

        # 택배 수거
        while pCap and ps:
            reduced = min(pickups[ps[-1]], pCap)
            pickups[ps[-1]] -= reduced
            pCap -= reduced

            if pickups[ps[-1]]:
                break
            ps.pop()
    
    return answer