1from collections import deque
2
3def solution(queue1, queue2):
4 sum1, sum2 = sum(queue1), sum(queue2)
5 dq1 = deque(queue1)
6 dq2 = deque(queue2)
7 cnt = 0
8
9 while cnt <= len(queue1)*2+1 and sum1 != sum2:
10 if sum1 > sum2:
11 tmp = dq1.popleft()
12 dq2.append(tmp)
13 sum1 -= tmp
14 sum2 += tmp
15 elif sum1 < sum2:
16 tmp = dq2.popleft()
17 dq1.append(tmp)
18 sum1 += tmp
19 sum2 -= tmp
20 cnt += 1
21
22 return cnt if sum1 == sum2 else -1
문제
- 길이가 같은 두 큐가 주어진다
- 두 큐의 합이 같아지도록 큐의 원소를 교환할 수 있는 최소 횟수를 구하라
- 큐의 pop은 왼쪽에서, push는 오른쪽에서 이루어진다
- TC
- input
queue1 : [3, 2, 7, 2], queue2 : [4 ,6, 5, 1]
- ouput
2
- input
해결방법
- deque를 이요해서 큐를 구현하였다
- 두 큐의 합이 같아질때까지, 합이 큰 큐에서 작은 큐로 원소를 이동시킨다
- 방법이 존재하지 않는 경우 무한루프가 발생하기 때문에, (큐의 길이)*2+1 만큼만 반복한다