[프로그래머스] 택배 배달과 수거하기 파이썬

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

프로그래머스

 

< 문제보기 >

 

내 코드

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

    while deliveries or pickups:
        a, b = cap, cap
        answer += max(len(deliveries), len(pickups)) * 2

        while len(deliveries) and a >= 0:
            deli = deliveries.pop()
            if deli <= a:
                a -= deli
            else:
                deliveries.append(deli - a)
                break

        while len(pickups) and b >= 0:
            pick = pickups.pop()
            if pick <= b:
                b -= pick
            else:
                pickups.append(pick - b)
                break

    return answer


# print(solution(2, 7, [1, 0, 2, 0, 1, 0, 2], [0, 2, 0, 1, 0, 2, 0]))

---

Review

 

cap의 개수만큼 배달 / cap 개수만큼 수거

하는 게 제일 좋은 그리디 전략이라고 생각했다.



알고리즘은 스택을 활용하여 생각을 했다.

이 그림은 그냥 내가 처음 문제 접근했을 때 적은 것이다.

 

---

다음은 예제를 Step으로 표현 해봤다.

 

cap = 4, n = 5

처음

deliveries = [1, 0, 3, 1, 2] (1번째 while 문)

pickups = [0, 3, 0, 4, 0] -> [0, 3, 0, 4] (2번째 while 문)

answer += max(len(deliveries), len(pickups)) * 2

 

1 Step (3번째 while 문 반복)

deliveries = [1, 0, 3, 1, 2] -> [1, 0, 2] (4번째 while 문)

pickups = [0, 3, 0, 4] -> [0, 3] (5번째 while 문)

answer += max(len(deliveries), len(pickups)) * 2

 

2 Step (3번째 while 문 반복)

deliveries = [1, 0, 2] -> [] (4번째 while 문) 

pickups = [0, 3] -> [] (5번째 while 문)

 

스택의 원소가 없으니 프로그램 종료