당신은 일렬로 나열된 n개의 집에 택배를 배달하려 합니다. 배달할 물건은 모두 크기가 같은 재활용 택배 상자에 담아 배달하며, 배달을 다니면서 빈 재활용 택배 상자들을 수거하려 합니다.
배달할 택배들은 모두 재활용 택배 상자에 담겨서 물류창고에 보관되어 있고, i번째 집은 물류창고에서 거리 i만큼 떨어져 있습니다. 또한 i번째 집은 j번째 집과 거리 j - i만큼 떨어져 있습니다. (1 ≤ i ≤ j ≤ n)
트럭에는 재활용 택배 상자를 최대 cap개 실을 수 있습니다. 트럭은 배달할 재활용 택배 상자들을 실어 물류창고에서 출발해 각 집에 배달하면서, 빈 재활용 택배 상자들을 수거해 물류창고에 내립니다. 각 집마다 배달할 재활용 택배 상자의 개수와 수거할 빈 재활용 택배 상자의 개수를 알고 있을 때, 트럭 하나로 모든 배달과 수거를 마치고 물류창고까지 돌아올 수 있는 최소 이동 거리를 구하려 합니다. 각 집에 배달 및 수거할 때, 원하는 개수만큼 택배를 배달 및 수거할 수 있습니다.
* 배달 및 수거 과정 예시는 위 링크를 참조해주세요!
트럭에 실을 수 있는 재활용 택배 상자의 최대 개수를 나타내는 정수 cap, 배달할 집의 개수를 나타내는 정수 n, 각 집에 배달할 재활용 택배 상자의 개수를 담은 1차원 정수 배열 deliveries와 각 집에서 수거할 빈 재활용 택배 상자의 개수를 담은 1차원 정수 배열 pickups가 매개변수로 주어집니다. 이때, 트럭 하나로 모든 배달과 수거를 마치고 물류창고까지 돌아올 수 있는 최소 이동 거리를 return 하도록 solution 함수를 완성해 주세요.
이 문제는 그리디로 접근할 수 있다. 한 번 물류센터에서 이동할 때마다 0이 아닌 최대 배달지 거리와 최대 수거지 거리 중 가장 큰 값만큼 이동하면 최소 거리로 이동할 수 있기 때문이다. 따라서 이에 맞추어 코드를 작성해 주면 된다. 한 번의 iteration동안 0이 아닌 최대 거리를 먼저 찾고, 그리고 최대 cap에 맞추어 배달 리스트와 수거 리스트를 제거해나가면 풀 수 있는 문제이다.
실제 테스트 당시에는 구조상의 비효율성 때문에 시간초과를 몇 번 겪어서 멘붕 직전까지 몰렸었다. 다행히 풀이는 성공했지만 코테 연습과 실전의 차를 보여 준 뜻있는 문제인 듯 싶다.
풀이 코드
def solution(cap, n, deliveries, pickups):
answer = 0
while deliveries or pickups :
deliver_cap, pickup_cap = cap, cap
while deliveries and deliveries[-1] == 0 :
deliveries.pop()
while pickups and pickups[-1] == 0 :
pickups.pop()
answer += max(len(deliveries), len(pickups))*2
while deliveries and deliver_cap > 0:
box = deliveries.pop()
if box <= deliver_cap :
deliver_cap -= box
else :
deliveries.append(box - deliver_cap)
break
while pickups and pickup_cap > 0 :
box = pickups.pop()
if box <= pickup_cap :
pickup_cap -= box
else :
pickups.append(box - pickup_cap)
break
return answer
