풀이

개인적으로 최근 들어 가장 어려운 level2 문제였다.

이 문제의 핵심은 택배 출발 지점부터 생각하는게 아닌, 끝 지점 부터 생각하는 것이다.
배달과 수거 둘 중 가장 멀리 있는 곳을 기준으로 삼아야 한다.

• 가장 먼저 시작하기 전 가장 멀리 있는 택배물을 찾기 위해 루프를 돌면서 0이 나오면 pop을 해서 없앤다.
  • 만약 배달과 수거 둘 다 전부 없어졌다면 배달할 곳과 수거할 곳이 없는 것이기 때문에 0을 리턴하면 된다.
• 무한 루프를 돌면서 택배차에 실을 수 있는 최대치가 될 때까지 count를 새면서 리스트의 요소값을 없애간다.
  • 예를 들면 cap = 4이고, del = [1, 2, 3, 4], pick = [2, 3, 2, 1]이면
  • del = [1, 2, 3], pick = [2, 3]이 된다.
  • 왜냐면 4개를 실을 수 있으니 배달은 가장 맨 끝에 4개 배달가면 끝이고, 오면서 pick의 끝에서부터 1개 2개를 수거하면 차에 실을 수 있는 최대치를 넘어서지 않는다.
  • 그렇다면 pick에서 [2, 3]만 남는데, 차에는 1개를 더 실을 수 있는 상태이다.
  • 그래서 마지막에 차에 실을 수 있는 만큼 pick에서 마지막 인덱스에 접근해서 실을 수 있는 갯수만큼 빼준다.
  • 그렇다면 첫번째 시도로 del = [1, 2, 3], pick = [2, 2]가 된다.
• 다음 택배 배달원은 무조건 del와 pick의 길이가 긴 것으로 이동할 것이다.
  • del의 길이가 3이며, pick의 길이가 2이기 때문에 배달원은 적어도 6만큼 이동하게 될 것이다.
  • 그렇기 때문에 무한 루프를 시작하자마자 택배 기사가 미래에 움직일 거리를 미리 계산 해놔야 한다.

풀이가 잘 이해가지 않는다면 코드를 먼저 보고 풀이를 봐주시면 됩니다.

코드

def solution(cap, n, deliveries, pickups):
    answer = 0

    while deliveries or pickups:
        if deliveries[-1] != 0 or pickups[-1] != 0:
            break
        if deliveries and deliveries[-1] == 0:
            deliveries.pop()
        if pickups and pickups[-1] == 0:
            pickups.pop()

    while deliveries or pickups:
        answer += max(len(deliveries), len(pickups)) * 2
        if deliveries:
            if deliveries[-1] > cap:
                deliveries[-1] -= cap
            else:
                cnt = 0
                while deliveries and deliveries[-1] + cnt <= cap:
                    cnt += deliveries.pop()
                if deliveries:
                    deliveries[-1] -= cap - cnt
        if pickups:
            if pickups[-1] > cap:
                pickups[-1] -= cap
            else:
                cnt = 0
                while pickups and pickups[-1] + cnt <= cap:
                    cnt += pickups.pop()
                if pickups:
                    pickups[-1] -= cap - cnt
    return answer