[99클럽/파이썬 챌린저/30일차] 택배 배달과 수거하기

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

 

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

입출력 예

cap	n	deliveries	pickups	result
4	5	[1, 0, 3, 1, 2]	[0, 3, 0, 4, 0]	16
2	7	[1, 0, 2, 0, 1, 0, 2]	[0, 2, 0, 1, 0, 2, 0]	30

 

 

배달 혹은 수거 중 가장 먼 곳부터 가는 탐욕적인 방법을 선택했다.

배달 이후에 지나온 모든 집에 들르면서 돌아올 수 있으므로, 수거 단계에서 배달을 고려하지 않았다.

 

현재 남아있는 배달 혹은 수거 중 제일 먼 곳으로 선택하고, 최대치를 채울 때까지 배달과 수거를 했다.

 

 

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

    i = n-1
    j = n-1
    answer = 0
    while i>=0 or j>=0:
        del_cnt = 0
        while i >= 0:
            if deliveries[i] != 0: break
            i -= 1
        ci = i
        while i >= 0 and del_cnt<cap:
            if deliveries[i] + del_cnt <= cap:
                del_cnt += deliveries[i]
                deliveries[i] = 0
                i -= 1
                continue
            else:
                deliveries[i] -= cap-del_cnt
                del_cnt = cap

        
        pick_cnt = 0
        while j >= 0:
            if pickups[j] != 0: break
            j -= 1
        cj = j
        while j >= 0 and pick_cnt<cap:
            if pickups[j] + pick_cnt <= cap:
                pick_cnt += pickups[j]
                pickups[j] = 0
                j -= 1
                continue
            else:
                pickups[j] -= cap-pick_cnt
                pick_cnt = cap

        if ci >= 0 or cj>=0:
            answer += (max(ci, cj)+1) * 2

    return answer​

 

---