택배 배달과 수거하기
문제 설명 이외에 제한 사항은 생략하였다. 필요한 부분은 언급하며 진행할텐데 모든 정보를 적을 필요는 없다고 판단하여 적지 않았다
시간 초과 해결
원인
import copy
def remove_last_element_zero(arr):
arr = copy.deepcopy(arr)
while arr and arr[-1] == 0:
arr.pop()
return arr
해결
def remove_last_element_zero(arr):
while arr and arr[-1] == 0:
arr.pop()
return arr
deep copy 를 통해 원본 배열을 수정하지 않게하려하였으나 시간 초과가 발생하였다. deep copy 하지 않고 원본 배열을 수정하니 시간 초과가 발생하지 않았다.
문제 설명
당신은 일렬로 나열된 n개의 집에 택배를 배달하려 합니다. 배달할 물건은 모두 크기가 같은 재활용 택배 상자에 담아 배달하며, 배달을 다니면서 빈 재활용 택배 상자들을 수거하려 합니다. 배달할 택배들은 모두 재활용 택배 상자에 담겨서 물류창고에 보관되어 있고, i번째 집은 물류창고에서 거리 i만큼 떨어져 있습니다. 또한 i번째 집은 j번째 집과 거리 j - i만큼 떨어져 있습니다. (1 ≤ i ≤ j ≤ n) 트럭에는 재활용 택배 상자를 최대 cap개 실을 수 있습니다. 트럭은 배달할 재활용 택배 상자들을 실어 물류창고에서 출발해 각 집에 배달하면서, 빈 재활용 택배 상자들을 수거해 물류창고에 내립니다. 각 집마다 배달할 재활용 택배 상자의 개수와 수거할 빈 재활용 택배 상자의 개수를 알고 있을 때, 트럭 하나로 모든 배달과 수거를 마치고 물류창고까지 돌아올 수 있는 최소 이동 거리를 구하려 합니다. 각 집에 배달 및 수거할 때, 원하는 개수만큼 택배를 배달 및 수거할 수 있습니다.
흐름 파악
흐름 파악을 위해 꼬리에 꼬리를 무는 방식으로 접근하려한다.
반환해야하는 값은 뭐야?
택배 상자를 배달하고 수거하는데 걸리는 최소 이동 거리
배달과 수거를 어떻게 해야해?
우선 배달을 먼저하고 돌아오면서 수거를 하면 돼!
배달 위치를 어디로 정해야해?
가장 멀리 있는 곳부터 배달하면 돼!
어찌되었든 가장 멀리 있는 곳도 방문해야하기 때문에 배달과 수거는 가장 멀리 있는 곳부터 해야한다. 멀리 있는 곳부터 배달하면서 수거를 하면서 돌아오면 된다.
Pseudo Code
def 배달_또는_회수(arr):
if arr가 비어있으면:
return
amount = 0
while arr가 비어있지 않고 amount가 cap보다 작으면:
if cap < amount + arr[-1]:
value = cap - amount
amount += value
arr[-1] -= value
break
amount += arr[-1]
arr.pop()
while 배달 또는 회수할 곳이 남아 있으면:
배달 = 뒤에서부터_0인_원소_제거
회수 = 뒤에서부터_0인_원소_제거
가장_먼_지역_인덱스 = max(len(배달), len(회수)) - 1
배달_또는_회수(배달)
배달_또는_회수(회수)
answer += 이동 거리 * 2 # 왕복이기 때문
return answer
실제 코드
def remove_last_element_zero(arr):
while arr and arr[-1] == 0:
arr.pop()
return arr
def solution(cap, n, deliveries, pickups):
answer = 0
def delivery_or_pickup(arr):
if not arr:
return
amount = 0
while arr and not amount == cap:
if cap < amount + arr[-1]:
value = cap - amount
amount += value
arr[-1] -= value
break
amount += arr[-1]
arr.pop()
while deliveries or pickups:
deliveries = remove_last_element_zero(deliveries)
pickups = remove_last_element_zero(pickups)
furthest_delivery_index = max(len(deliveries), len(pickups)) - 1
delivery_or_pickup(deliveries)
delivery_or_pickup(pickups)
answer += (furthest_delivery_index + 1) * 2
return answer
print(solution(4, 100000, [1 for _ in range(100000)], [1 for _ in range(100000)]), 2500100000)
print(solution(2, 7, [1, 0, 2, 0, 1, 0, 2], [0, 2, 0, 1, 0, 2, 0]), 30)
print(solution(2, 7, [0, 0, 0], [0, 0]), 0)
print(solution(4, 5, [1, 0, 3, 1, 2], [0, 0, 0, 0, 0]), 16)
print(solution(4, 5, [1, 0, 3, 0, 0], [0, 3, 0, 4, 0]), 12)
print(solution(1, 7, [1, 0, 2, 0, 1, 0, 2], [0, 2, 0, 1, 0, 2, 0]), 52)