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

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

프로그래머스

 

문제 설명

당신은 일렬로 나열된 n개의 집에 택배를 배달하려 합니다. 
배달할 물건은 모두 크기가 같은 재활용 택배 상자에 담아 배달하며, 
배달을 다니면서 빈 재활용 택배 상자들을 수거하려 합니다.
배달할 택배들은 모두 재활용 택배 상자에 담겨서 물류창고에 보관되어 있고, 
i번째 집은 물류창고에서 거리 i만큼 떨어져 있습니다. 
또한 i번째 집은 j번째 집과 거리 j - i만큼 떨어져 있습니다. (1 ≤ i ≤ j ≤ n)
트럭에는 재활용 택배 상자를 최대 cap개 실을 수 있습니다. 
트럭은 배달할 재활용 택배 상자들을 실어 물류창고에서 출발해 각 집에 배달하면서, 
빈 재활용 택배 상자들을 수거해 물류창고에 내립니다. 
각 집마다 배달할 재활용 택배 상자의 개수와 수거할 빈 재활용 택배 상자의 개수를 알고 있을 때, 
트럭 하나로 모든 배달과 수거를 마치고 물류창고까지 돌아올 수 있는 최소 이동 거리를 구하려 합니다. 
각 집에 배달 및 수거할 때, 원하는 개수만큼 택배를 배달 및 수거할 수 있습니다.

다음은 cap=4 일 때, 최소 거리로 이동하면서 5개의 집에 배달 및 수거하는 과정을 나타낸 예시입니다.
16(=5+5+3+3)의 거리를 이동하면서 모든 배달 및 수거를 마쳤습니다. 
같은 거리로 모든 배달 및 수거를 마치는 다른 방법이 있지만, 
이보다 짧은 거리로 모든 배달 및 수거를 마치는 방법은 없습니다.

트럭에 실을 수 있는 재활용 택배 상자의 최대 개수를 나타내는 정수 cap, 
배달할 집의 개수를 나타내는 정수 n, 
각 집에 배달할 재활용 택배 상자의 개수를 담은 1차원 정수 배열 deliveries와 
각 집에서 수거할 빈 재활용 택배 상자의 개수를 담은 1차원 정수 배열 pickups가 
매개변수로 주어집니다. 이때, 트럭 하나로 모든 배달과 수거를 마치고 
물류창고까지 돌아올 수 있는 최소 이동 거리를 return 하도록 solution 함수를 완성해 주세요.

---

제한사항

1 ≤ cap ≤ 50
1 ≤ n ≤ 100,000
deliveries의 길이 = pickups의 길이 = n
deliveries[i]는 i+1번째 집에 배달할 재활용 택배 상자의 개수를 나타냅니다.
pickups[i]는 i+1번째 집에서 수거할 빈 재활용 택배 상자의 개수를 나타냅니다.
0 ≤ deliveries의 원소 ≤ 50
0 ≤ pickups의 원소 ≤ 50
트럭의 초기 위치는 물류창고입니다.

---

풀이

 

로직

짐을 먼저 풀로 싣고
> deliveries, pickups의 끝에있는 0 처리
> deliveries의 먼 집부터 짐 내림 이동거리 기록
> pickups의 먼 집부터 집 내림 이동거리 기록
> 이동 거리 비교 후 더 먼곳을 answer에 2배로 저장(왕복)
> deliveries와 pickups가 빈 list가 될 때까지 반복

 

초기 구현

# 초기 구현
def solution(cap, n, deliveries, pickups):
    answer = 0
    while deliveries and not deliveries[-1]:
        deliveries.pop()
    while pickups and not pickups[-1]:
        pickups.pop()
    while True:
        current_load = 0
        farthest_delivery = 0
        empty = cap
        while empty!=0 and deliveries:
            last = deliveries.pop()
            if not last: continue
            farthest_delivery = max(len(deliveries)+1,farthest_delivery)
            if last > empty:
                last -= empty
                deliveries.append(last)
                empty=0
                break
            current_load += last
            empty = cap - current_load

        current_load = 0
        farthest_pickup = 0
        empty = cap
        while empty!=0 and pickups:
            last = pickups.pop()
            if not last: continue
            farthest_pickup = max(len(pickups)+1,farthest_pickup)
            if last > empty:
                last -= empty
                pickups.append(last)
                empty=0
                break
            current_load += last
            empty = cap - current_load

        answer += max(farthest_delivery,farthest_pickup)*2
        if not deliveries and not pickups: break
    return answer
# 3061.43ms

 

뭔가 읽기가 너무 힘들다.

중복되는 코드가 너무 많음, 배달하는 것과 수거하는 것이 로직은 같아서 2번씩 중복이 된다.

또 비효율적으로 짠 코드도 있기때문에 그 부분을 중점으로 수정을 해봤다.

 

1차 수정 : 필요 없는 로직 정리 

# 1차 수정 : 필요없는 로직 정리
def solution(cap, n, deliveries, pickups):
    answer = 0
    while deliveries or pickups:
        while deliveries and not deliveries[-1]:
            deliveries.pop()
        while pickups and not pickups[-1]:
            pickups.pop()
        
        farthest_delivery = len(deliveries)
        empty = cap
        while empty and deliveries:
            last = deliveries.pop()
            if last > empty:
                last -= empty
                deliveries.append(last)
                empty = 0
            else: empty -= last

        farthest_pickup = len(pickups)
        empty = cap
        while empty and pickups:
            last = pickups.pop()
            if last > empty:
                last -= empty
                pickups.append(last)
                empty = 0
            else: empty -= last

        answer += max(farthest_delivery,farthest_pickup) * 2
    return answer
# 1839.64ms

 

여전히 쉽게 읽히지 않는 코드. 중복되는 부분을 함수로 바꾸면 훨씬 보기 편할것 같다.

 

2차 수정 : 중복 코드 함수 처리

# 2차 수정 : 중복 코드 함수 처리
def delivery_process(arr, cap):
    while arr and not arr[-1]:
        arr.pop()
    farthest = len(arr)
    while cap and arr:
        last = arr.pop()
        if last > cap:
            last -= cap
            arr.append(last)
            cap = 0
        else: cap -= last
    return farthest

def solution(cap, n, deliveries, pickups):
    answer = 0
    while deliveries or pickups:
        farthest_delivery = delivery_process(deliveries, cap)
        farthest_pickup = delivery_process(pickups, cap)
        answer += max(farthest_delivery,farthest_pickup)
    return answer * 2
# 1815.67ms

 

훨씬 읽기 편해졌다. 시간은 큰 차이가 안나지만 가독성이 좋아진다면

충분히 의미있는 리팩토링이라고 생각하기때문에 만족이다.

 

인상 깊은 풀이

# 팀원이 푼 시간복잡도 n으로 풀기
def solution(cap, n, dels, pics):
    answer = 0
    packet_on_deliver=0
    box_on_recall=0
    for i,(p,b) in enumerate(zip(dels[::-1],pics[::-1])):
        visit1,r1=divmod(p-packet_on_deliver,cap)
        visit2,r2=divmod(b-box_on_recall,cap)
        
        if packet_on_deliver>=p and box_on_recall>=b:
            packet_on_deliver -=p
            box_on_recall -= b
        else:
            aditional_visit_count=max(visit1+(1 if r1 else 0),visit2+(1 if r2 else 0))
            packet_on_deliver +=aditional_visit_count*cap - p
            box_on_recall +=aditional_visit_count*cap - b
            answer += aditional_visit_count*(n-i)*2
    return answer
# 84.84ms

 

추가로 알고리즘 스터디 팀원이 시간복잡도 O(n)으로 푸는 코드를 가져왔고 살짝 벽느꼈다.

 

로직은 다음과 같다

 

dels와 pics 리스트를 역순으로 순회하면서 각 패키지의 배달 및 회수에 필요한 방문 횟수를 계산

> 현재 배달 및 회수 가능한 패키지 수를 확인하고, 필요한 추가 방문 횟수를 계산

> 필요한 추가 방문 횟수만큼 패키지를 배달하거나 회수하고, 해당 횟수를 answer에 더함

 

주어진 문제를 직관적인 해결방법이 아닌 수학적 논리로 푸는게 너무 멋있다.