프로그래머스 택배 배달과 수거하기 | python | 그리디

문제

링크

풀이

• 그리디하게 풀어내는 문제이다.
• 풀이 순서는 다음과 같다
  1. pop()을 통해 배달/수거를 해야하는 가장 먼 집을 찾는다.
  2. answer는 배달/수거를 해야하는 가장 먼 거리에 2를 곱하여 더해준다. 2를 곱하는 이유는 왕복거리를 계산하기 위함이다.
  3. 배달 및 수거는 독립적인 행위로 생각할 수 있다. 따라서 cap 만큼 수용 가능한 box를 각각 만들어 아래의 과정을 수행한다.
     1. 가장 먼 집부터 차례로 들리면서 box + 현재 집의 배달/수거 값이 cap 보다 작거나 같다면 box에 현재 집의 배달/수거 값을 그대로 더해준다. 해당 집의 배달/수거 값은 이제 0이 되었으므로 pop()을 수행하여 배달/수거를 해야하는 가장 먼 집을 업데이트 해준다.
     2. box + 현재 집의 배달/수거 값이 cap 보다 크다면 남은 box 용량 만큼만 현재 집의 배달/수거 값을 더해주고 while문을 빠져나온다.
  4. 모든 배달과 수거를 마치고 돌아올 때까지 2-3을 반복한다.

"""
2023.11.06
"""


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:
        answer += max(len(deliveries), len(pickups)) * 2

        box = 0
        while box <= cap and deliveries:
            if deliveries[-1] + box <= cap:
                box += deliveries.pop()
            else:
                deliveries[-1] -= cap - box
                break

        box = 0
        while box <= cap and pickups:
            if pickups[-1] + box <= cap:
                box += pickups.pop()
            else:
                pickups[-1] -= cap - box
                break
    return answer

more

보통은 접근 방식에서 막혀서 풀이를 보게 되는 경우가 대부분인데 해당 문제는 접근 방식은 빠르게 떠올렸음에도 막상 코드로 작성하려드니 어려웠던 문제이다.

필자는 이미 배달/수거 완료한 지점을 업데이트 해야하는 부분에서 막혔었다. 처음엔 0이 아닌 가장 먼 거리의 집의 인덱스를 특정 변수에 저장해두고 계속 업데이트 하는 방식으로 진행하려 했는데 너무 복잡하게 생각하는 것 같아서 결국 다른 풀이를 확인했다.

풀이를 보다보니 while문과 pop()을 활용해서 배달/수거 완료를 나타내는 것이 가장 직관적이여 보여 본인도 이를 활용해 풀이를 마쳤다. 물론 5개의 while문은 보자마자 다소 거부감을 일으키게 했다

유의할 점은 while문 내에서 pop()을 활용할 땐 꼭 배열의 크기를 확인해야한다는 것이다. 배열 내 원소가 없을 경우 index error가 발생함을 잊지말자.