문제

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

접근방식

우선 일직선 상의 배열 상에서 최소 거리를 구하는 문제이다.
단정 지으면 안되지만, 이런 문제에서는 다이나믹 프로그래밍(DP) 와 그리디 알고리즘이 떠오른다. 거기 추가로 BFS와 같은 그래프 탐색을 적용하는 경우도 있다.
이 문제의 조건은 크게

• 택배를 실을 수 있는 수가 정해져 있다.
• 각 집에는 배달할 택배의 개수와 수거 할 택배의 박스가 있다.
• 배달 택배와 수거하는 택배는 동일한 택배로 본다.
• 0번 인덱스에서 출발하여 택배박스를 0번에 다시 놓기 위해 왕복을 해야한다.

문제를 보면 N도 충분히 크지 않고 그리디는 떠올리기 어렵지는 않았던 것 같다.
근데 택배의 개수와 최소 거리 둘 중 어느 요소에 그리디 알고리즘을 적용해야하는지를 나는 어려워했었다.
정답은 둘 다 였다..
카카오의 해설에서는 이를 stack을 활용한 그리디 알고리즘이라고 설명한다.
문제 해결의 키포인트는 두가지 이다.

1. 오른쪽으로 이동할 때 최대한 많은 택배를 배달하고, 돌아올때는 최대한 많은 택배를 수거한다.
2. 가장 멀리 있는 집 부터 배달하고, 수거한다.

이를 stack 으로 구현한다면,
1. 배달 스택, 수거 스택 2가지의 스택을 만든다.
2. 택배가 0개보다 많은 집의 인덱스를 0번 인덱스부터 스택에 차례대로 넣는다.
3. 그러면 스택의 최상단(top)에는 가장 멀리있는 집이 있다.
4. 택배를 배달하러 출발할 집을 초기에 정할때는 배달 스택과 수거 스택 최상단을 비교하여, 더 큰 집을 가장 멀리 갈 집으로 정한다.

위의 알고리즘을 적용하면 오른쪽으로 이동하면서 가장 많은 택배를 배달하고, 돌아오면서 가장 많은 택배를 수거할 수 있다.

정답코드

def solution(cap, n, deliveries, pickups):
    answer = 0
    deliver_stack, pickup_stack = [], []
    for i in range(n):
        if deliveries[i] != 0:
            deliver_stack.append(i)
        if pickups[i] != 0:
            pickup_stack.append(i)
    while deliver_stack or pickup_stack:
        flag = cap
        if len(deliver_stack) == 0 and len(pickup_stack) != 0:
            answer += (pickup_stack[-1] + 1) * 2
        elif len(deliver_stack) != 0 and len(pickup_stack) == 0:
            answer += (deliver_stack[-1] + 1) * 2
        elif deliver_stack[-1] >= pickup_stack[-1]:
            answer += (deliver_stack[-1] + 1) * 2
        else:
            answer += (pickup_stack[-1] + 1) * 2
        while deliver_stack and flag != 0:
            index = deliver_stack.pop()
            if deliveries[index] <= flag:
                flag -= deliveries[index]
                deliveries[index] = 0
            else:
                deliveries[index] -= flag
                flag = 0
                deliver_stack.append(index)
        flag = cap - flag
        while pickup_stack and flag != 0:
            index = pickup_stack.pop()
            if pickups[index] <= flag:
                flag -= pickups[index]
                pickups[index] = 0
            else:
                pickups[index] -= flag
                flag = 0
                pickup_stack.append(index)
    return answer

코드해석

        if len(deliver_stack) == 0 and len(pickup_stack) != 0:
            answer += (pickup_stack[-1] + 1) * 2
        elif len(deliver_stack) != 0 and len(pickup_stack) == 0:
            answer += (deliver_stack[-1] + 1) * 2
        elif deliver_stack[-1] >= pickup_stack[-1]:
            answer += (deliver_stack[-1] + 1) * 2
        else:
            answer += (pickup_stack[-1] + 1) * 2

초기에 택배 차가 갈 가장 멀리 있는 집을 정하는 과정이다.
수거해야할 집과 배달할 집 중 한번에 갈때 거리가 제일 큰 집으로 이동해야하고, 왕복을 해야하므로 *2를 해주어야한다.

        while deliver_stack and flag != 0:
            index = deliver_stack.pop()
            if deliveries[index] <= flag:
                flag -= deliveries[index]
                deliveries[index] = 0
            else:
                deliveries[index] -= flag
                flag = 0
                deliver_stack.append(index)
        # 돌아올때 택배를 수거하기 위해 택배차의 공간을 초기화해준다.        
        flag = cap - flag

오른쪽으로 이동하면서 최대한 많은 택배를 배달 하는 코드이다.
deliver_stack에 멀리있는 택배부터 배달을 하지만 flag = cap 최대 수용량을 넘지 않게 신경써주는 것도 중요하다.

        while pickup_stack and flag != 0:
            index = pickup_stack.pop()
            if pickups[index] <= flag:
                flag -= pickups[index]
                pickups[index] = 0
            else:
                pickups[index] -= flag
                flag = 0
                pickup_stack.append(index)

이제 돌아오면서 수거할 택배의 수를 정하는 과정이다.
이렇게 한 싸이클이 끝나고, 택배 스택과 수거 스택에 남아있는 택배가 있다면 위의 과정을 반복하고, 남아있는 택배가 없다면 배달이 됐으므로 answer를 return 해주면 된다.