[Programmers] P150369 택배 배달과 수거하기

[Programmers] P150369 택배 배달과 수거하기

Question

Language: Python

주어진 문제의 조건에 택배 배달 및 수거 전략을 세워 최소한의 이동거리를 통해 모든 과정을 처리하는 것이다.

제일 먼 거리에서부터 가장 가까운 거리에 있는 집까지 순차적으로 택배와 수거를 처리하게 되면 최소 이동거리를 가지게 된다. 택배를 처리하고 난 다음에는 오는 길에는 수거를 하면 되기 때문에, 사실상 택배를 가야하는 가장 먼 거리와 수거를 가야하는 마지막 거리를 비교해서 그 만큼의 2배 거리값이 한번의 이동과정에서 발생하는 이동이다.

그래서, 가장 마지막에서 부터 순차적으로 처리하기 위해 알맞은 자료구조가 바로 stack이다.

stack 처리

stack을 이용해서 한번의 이동과정에서 가장 멀리 이동해야하는 집의 위치를 알아낸다.

def find_farest_house(stack,cap):
    total_parcels=0
    max_distance=0
    while stack:  
        #스택 top
        index,count=stack[-1]
        #거리 갱신
        max_distance=max(max_distance,index)
        #만약 top 위치의 집에 있는 택배 혹은 수거를 모두 처리하더라도 최대 용량을 넘어서지 않는 경우 pop 하고 다음 값을 검증한다.
        if total_parcels + count <= cap:
            max_distance=max(max_distance,index)
            total_parcels+=count
            stack.pop(-1)
        #만약 해당 집에서 모든 택배, 수거를 처리하였을 때 최대 용량을 넘어서는 경우, 최대 용량에 도달할 때까지의 양만 처리하고 반복문을 탈출한다.
        else:
            stack[-1][1]-=(cap-total_parcels)
            total_parcels=cap
            break
    return max_distance

Solution

def find_farest_house(stack,cap):
    total_parcels=0
    max_distance=0
    while stack:  
        #스택 top
        index,count=stack[-1]
        #거리 갱신
        max_distance=max(max_distance,index)
        #만약 top 위치의 집에 있는 택배 혹은 수거를 모두 처리하더라도 최대 용량을 넘어서지 않는 경우 pop 하고 다음 값을 검증한다.
        if total_parcels + count <= cap:
            max_distance=max(max_distance,index)
            total_parcels+=count
            stack.pop(-1)
        #만약 해당 집에서 모든 택배, 수거를 처리하였을 때 최대 용량을 넘어서는 경우, 최대 용량에 도달할 때까지의 양만 처리하고 반복문을 탈출한다.
        else:
            stack[-1][1]-=(cap-total_parcels)
            total_parcels=cap
            break
    return max_distance
    
def solution(cap, n, deliveries, pickups):
    answer = 0
    
    delivery_stack=[[i+1,count] for i,count in enumerate(deliveries) if count > 0]
    pickup_stack=[[i+1,count] for i,count in enumerate(pickups) if count > 0]
    #택배, 수거 스택이 모두 빌때까지 계속 반복한다.
    while delivery_stack or pickup_stack:        
        #택배를 가야하는 가장 먼 거리 와 수거를 가야하는 가장 먼 거리를 비교해서, 더 큰 값이 한번의 이동에서의 이동거리가 된다.
        max_distance=max(find_farest_house(delivery_stack,cap),find_farest_house(pickup_stack,cap))
        answer+=2*max_distance

    return answer