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

문제 링크 : https://school.programmers.co.kr/learn/courses/30/lessons/150369

프로그래머스

최소 이동거리를 구하기 위해서는 가는 길에 배달을 하고 오는 길에 회수를 하는 방법이 있다.

따라서 배달을 하는 경우와 회수를 하는 경우로 두 가지를 나누어서 반복문을 수행하여야 한다.

 

코드를 작성하기 위한 순서는 다음과 같다.

1. deliveries와 pickups 각각의 마지막 원소가 모두 0일 경우, 해당 구역은 방문할 필요 없으므로 제거해준다.

2. 배달을 하는 경우, deliveries의 마지막 원소가 cap보다 작으면 모두 배달할 수 있고 그 전 원소도 배달할 수 있기 때문에 반복문을 사용하여 어디까지 한 번에 배달할 수 있는지 구한다.

3. 회수를 하는 경우도 마찬가지이다. pickups의 마지막 원소가 cap보다 작으면 모두 회수할 수 있고 그 전 원소도 회수할 수 있기 때문에 이 또한 한 번에 회수할 수 있는 구역을 구한다.

 

def solution(cap, n, deliveries, pickups):
    answer = 0
    
    while deliveries or pickups: #1번
        if deliveries[-1] == 0 and pickups[-1] == 0:
            deliveries.pop()
            pickups.pop()
        else:
            break
            
    while deliveries or pickups:
        now = 0
        answer += max(len(deliveries), len(pickups))*2 #왕복 움직이는 거리이므로 곱하기 2를 해준다.
        while deliveries: #2번
            d = deliveries.pop()
            if now+d > cap: #cap보다 커서 한 번에 배달할 수 없는 경우
                d -= cap-now
                now = 0 #가지고 있는 택배를 모두 배달하였으므로 0으로 초기화해준다.
                deliveries.append(d) #해당 집의 택배를 모두 배달한 것이 아니기 때문에 append를 해준다.
                break
            else: #cap보다 작아서 모두 배달을 한 경우
                now += d #배달한 택배 갯수를 더해준다. (빼지 않고 더하는 이유는 아래에 상세하게 있습니다.)

        now = 0
        while pickups: #3번
            p = pickups.pop()
            if p+now > cap: #cap보다 커서 한 번에 회수할 수 없는 경우
                p -= cap-now
                now = 0
                pickups.append(p)
                break
            else: #cap보다 작아서 모두 회수를 할 경우
                now += p
                
    return answer

 

해당 풀이의 포인트는 now = cap을 하지 않고 now = 0으로 초기화했다는 점이다.

now = cap으로 초기화하여 배달할 때마다 빼주지 않는 이유는 cap=4이고 deliveries와 pickups가 각각 [0, 0, 1, 2], [0, 4, 0, 0]일 때, now를 4로 초기화하고 3, 4번째 집에 배달을 하면 cap이 1이 되어 2번째 집을 회수할 때, 3개만 회수할 수 있는 문제가 발생하기 때문에 최소 이동거리를 구할 수 없기 때문이다. 

또한 2번 조건을 인지하는 것도 중요했다. (처음에 2번만 틀려서 몹시 당황했어요 ㅠㅠ)

항상 아예 되지 않거나 되는 경우를 판단하여 따로 분류하는 것을 먼저 생각해야겠다.