[Python] 프로그래머스 택배 배달과 수거하기(탐욕 알고리즘)

이번 문제는 Level2 문제입니다.  탐욕 알고리즘을 사용하면 풀 수 있는 문제입니다.

 

문제의 링크입니다.

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

프로그래머스

 

문제는 등간격을 가지는 집들이 택배사를 기점으로 있을 때, 각각의 집에서 요청한 택배의 개수와 수거품들을 최소한의 거리 이동으로 모두 처리하는 문제입니다.

 

그림에서와 같이 왼쪽에 택배사가 있고, 여러 집들이 1의 거리를 사이로 위치하고 있습니다.  택배차에는 실을 수 있는 택배 상자의 개수가 제한되어 있습니다.  그럴경우 각 집에 배달과 수거를 함께 해야 합니다.

 

	#1	#2	#3	#4	#5	#6
배달		2		1	3	2
수거	3		2	4	1

위와 같이 배달할 물건과 수거할 물건이 있을 때, 택배사는 배달할 물건과 수거할 물건을 적절하게 스케쥴링하면 가장 짧은 거리를 이동할 수 있습니다.

 

택배사의 트럭이 4개의 물건을 최대 실을 수 있다면, 

1) #5 2개, #6 2개 물건을 싣고 이동하면서 배달 (누적거리 6)

2) #5에서 1개 수거, #4에서 3개 수거후 귀환 (누적거리 12)

3) #2 물건, #4 물건 #5 물건을 싣고 이동하면서 배달 (누적거리 17)

4) #4 물건, #3 물건, #1 물건(1개) 수거후 귀환 (누적거리 22)

5) #1 물건 수거후 귀환 (누적거리 24)

 

그래서 최소 거리가 24가 됩니다.

 

이 알고리즘은 배달과 수거를 가장 먼거리에서부터 차례대로 택배 트럭 용량에 맞게 제거하고, 가장 긴 거리를 2배하여 누적하면 됩니다.

 

제가 작성한 소스입니다.

def solution(cap, n, deliveries, pickups):
    answer = 0
    while True:
        while len(deliveries) > 0 and deliveries[-1] == 0: deliveries.pop()
        while len(pickups) > 0 and pickups[-1] == 0: pickups.pop()
        if len(deliveries) == 0 and len(pickups) == 0: break
        answer += max(len(deliveries), len(pickups))*2
        tcap = cap
        while len(deliveries) > 0 and tcap > 0:
            if deliveries[-1] > tcap:
                deliveries[-1] -= tcap
                break
            tcap -= deliveries.pop()
        tcap = cap
        while len(pickups) > 0 and tcap > 0:
            if pickups[-1] > tcap:
                pickups[-1] -= tcap
                break
            tcap -= pickups.pop()            
    return answer