택배 배달과 수거하기(카카오) 문제풀이

문제 

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

프로그래머스

 

 

문제 접근 방식

문제 설명이 어렵게 되어 있어서 바로 예제를 통해 어떻게 진행되는지를 확인했다. 첫 예제의 경우 가장 먼 거리의 집부터 시작해서 갈 때 배달을 하고, 돌아올 때 먼 거리의 집의 물건을 수거하여 다음 수행할 거리를 단축시킨다. 예제에서는 처음 물건을 싣고 출발할 때 cap을 4임에도 물건을 3개 담아서 출발하는데 이 부분은 예제에서 약간의 혼동을 주기 위한 훼이크로 판단했다. 최대한 많이 싣고 가서 멀리 있는 집부터 배달하고, 이후 먼 거리부터 수거를 하면 되는 그리디 문제라 판단을 했고, 이를 검증하기 위해 예제2를 통해 손으로 그려가며 확인했다.

cap 만큼의 물건을 싣고, 멀리있는 집들의 배달 및 수거를 완료하여 이동하는 거리를 줄인다(그리디)

 

이를 구현할 때, 실제 택배가 왔다 갔다 하듯이 구현하면 for문을 여러번 수행하게 된다. 이렇게 하기 보다는 배달과 수거의 마지막 지점을 계속 저장해놓고 해당 위치부터 배달 및 수거를 해서 각 리스트를 갱신하고, 다음 마지막 위치를 갱신하는 방식을 반복하며 문제를 풀었다.

이때, 한번 이동하는 거리는 물류창고에서 가장 멀리 떨어진 배달 또는 수거 위치까지의 왕복거리이다. 

배달과 수거를 하는 방식
1. 1번 이동 거리 = max(배달 마지막 위치, 수거 마지막 위치) X 2
2. 각 배달과 수거의 마지막 위치에서 시작 -> cap을 감소시키며 배달 및 수거 진행(리스트 업데이트)
3. 각 배달과 수거의 마지막 위치를 갱신

 

시간 복잡도

각 함수 내부에서 많은 for문을 돌기 때문에 많은 시간이 걸릴 것 같으나, 사실상 리스트를 겹치지 않게 부분적으로 순회하기 때문에 전체적인 시간복잡도는 O(n) 이 된다. n의 시간복잡도가 1e5이므로 시간 내에 동작한다.

 

코드

# 기능 : 해당 리스트(배달 or 수거)의 마지막 물건이 있는 지점을 찾는다.
# 만약 -1 을 반환한다면 더이상 리스트에 남아있는 물건이 존재하지 않는다는 것.
def find_last_point(li, index):
    pivot = -1
    for i in range(index, -1, -1):
        if li[i] != 0: # 물건이 존재한다면 해당 위치를 반환한다.
            pivot = i
            break
    return pivot


# 기능 : 리스트의 마지막 지점에서 시작하여 물건을 배달 또는 수거 진행하여 리스트를 갱신하고, 마지막 수행 지점을 반환한다.
def update_list(li, pivot, cap):
    index = -1
    for i in range(pivot, -1, -1):
        if li[i] >= cap: # cap보다 물건량이 많다면 가능한 만큼만 물건을 배달(or 수거)하고 끝낸다.
            li[i] -= cap
            index = i
            break
        cap -= li[i]
        li[i] = 0
    return index


def solution(cap, n, deliveries, pickups):

    # 배달과 수거의 마지막 지점을 구한다.
    d_pivot = find_last_point(deliveries, n - 1)
    p_pivot = find_last_point(pickups, n - 1)

    answer = 0
    while True:
        # 배달과 수거 중 거리가 멀리 있는 위치까지의 거리를 구한다.
        distance = max(d_pivot, p_pivot) + 1

        if distance == 0: # 더이상 처리할 물건이 없는 상황 -> 종료
            break

        answer += distance * 2  ## 정답에 이동거리를 추가해준다.

        # 물건을 배달 및 수거하여 각 리스트의 값을 변경해준다.
        d_index = update_list(deliveries, d_pivot, cap)
        p_index = update_list(pickups, p_pivot, cap)

        # 수행이 완료된 지점에서 부터 다음에 배달 및 수거를 시작할 지점을 구한다.
        d_pivot = find_last_point(deliveries, d_index)
        p_pivot = find_last_point(pickups, p_index)

    return answer

 

 

회고

1. 호흡이 길고 문제 이해가 안되는 경우에는 예제를 통해 따라가며 이해하는 것이 도움이 된다.
2. 예제에서 풀이 과정 설명 시 훼이크를 넣는 경우도 존재한다.