가장 먼 택배 업무의 위치가 n이라고 했을때 왕복으로 2 * n을 움직이면서 수거와 배달 두가지 일을 할 수 있다는 아이디어만 떠올리면 풀립니다.
다만 구현할때 실수하기 쉬운 부분이 꽤 있었습니다. (빈 집을 뛰어넘기, 초기 데이터 정리 등등)
def solution(cap, n, deliveries, pickups):
answer = 0
pi, di = n, n
while not (pi == 0 and di == 0):
while pi >= 1 and pickups[pi - 1] == 0:
pi -= 1
while di >= 1 and deliveries[di - 1] == 0:
di -= 1
answer += (max(pi, di)) * 2
c = cap
while c > 0 and pi >= 1:
d = min(c, pickups[pi - 1])
pickups[pi - 1] -= d
c -= d
if pickups[pi - 1] == 0:
pi -= 1
c = cap
while c > 0 and di >= 1:
d = min(c, deliveries[di - 1])
deliveries[di - 1] -= d
c -= d
if deliveries[di - 1] == 0:
di -= 1
return answer
그리디 하게 합이 더 큰 쪽의 큐에서 수를 빼서 작은 쪽으로 넣으면 되는데, 이유는 조금만 생각해봐도 떠올릴 수 있습니다.
(큐의 선입선출 구조를 생각하시면 왜 그리디하게 풀이해서 정답이 나오는지 알 수 있습니다.)
입력된 리스트를 두개의 큐에 (Python의 경우 deque) 담고 그리디 하게 값을 빼고 넣어주며 같은 값이 되게 해 주면 됩니다.
실행시간을 단축시키는 가지치기가 몇개 가능한데, 우선 두 큐의 합을 더한 값이 홀수면 어떤 방법을 써도 같게 만들 수가 없습니다. 3을 정수로 2등분 시키는 게 불가능하듯이요.
2로 나눈 나머지가 0이 아니면 -1을 리턴하시면 됩니다. 그리고 큐의 합을 매번 구하지 않도록 초기 상태에서 합을 미리 구해놓은 다음, 옮기는 수만 합에서 직접 빼고 더해주면 매번 큐의 합을 구하는 것보다 빠르게 동작할 수 있습니다.
from collections import deque
def solution(queue1, queue2):
left = sum(queue1)
lqueue = deque(queue1)
right = sum(queue2)
rqueue = deque(queue2)
limit = 2 * (len(queue1) + len(queue2))
count = 0
if (left + right) % 2 == 1:
return -1
while count < limit:
if left == right:
return count
if left < right:
gap = rqueue.popleft()
left += gap
right -= gap
lqueue.append(gap)
else:
gap = lqueue.popleft()
right += gap
left -= gap
rqueue.append(gap)
count += 1
return -1
print(solution([3, 2, 7, 2], [4, 6, 5, 1]))