https://school.programmers.co.kr/learn/courses/30/lessons/118667
두 개의 큐가 주어지고, 각각 헤드에서 뽑은 값을 다른 큐의 테일에 넣을 수 있는 연산이 있고 그렇다.
처음에는 각각 뽑아보면서 테스트해야 싶었으나 그러면 연산이 너무 많아질 것 같아서 다른 방법을 찾아봤다.
queue1의 앞에서 뽑아서 queue2의 뒤로 가고, queue2의 앞에서 뽑아서 queue1의 뒤로 가면
이런 모양이기에 queue1을 뒤집으면
이렇게 되기에 두 큐를 합칠 수 있겠다 생각했다.
그래서 큐 두 개를 합치고 슬라이딩 윈도우로 해보았다.
def solution(queue1, queue2):
answer = -2
total = sum(queue1) + sum(queue2)
if total %2 != 0:
return -1
target = total // 2
combined = queue1 + queue2
n = len(queue1)
left = 0
right = n - 1
current = sum(queue1)
count = 0
while left < len(combined):
if current == target:
break
if current<target:
right += 1
right %= 2 * n
current += combined[right]
count += 1
else:
current -= combined[left]
left += 1
count += 1
return count if current == target else -1
큐 두 개를 합치고 슬라이딩 윈도우의 합을 전체 합의 1/2와 비교하면서 했다.
queue1부터 시작해서 left가 끝에 도달하지 않을 동안 크기를 비교하면서 크다면 left를 한 칸 오른쪽으로 옮기고, 작다면 right를 늘려서 증가시키고, 만약 right가 범위를 벗어나면 0번 인덱스로 옮겨서 더해줬다.
그래서 마지막에 left가 combined의 끝에 닿아서 멈추거나 current == target이 돼서 멈췄을 경우 current == target인지 비교해서 count나 -1을 출력했다.