두 큐의 합 같게 만들기
문제 Link
https://school.programmers.co.kr/learn/courses/30/lessons/118667 (opens in a new tab)
풀이
from collections import deque
def solution(queue1, queue2):
ans = 0
s1 = sum(queue1)
s2 = sum(queue2)
queue1 = deque(queue1)
queue2 = deque(queue2)
length = len(queue1)
# 총 합이 홀 수인경우 절대 정답이 나올 수 없음
if (s1 + s2) % 2 :
return -1
while ans < length * 4 :
if s1 == s2 :
return ans
if s1 > s2 :
v = queue1.popleft()
s1 -= v
s2 += v
queue2.append(v)
else :
v = queue2.popleft()
s1 += v
s2 -= v
queue1.append(v)
ans += 1
return -1
배운점
- 합을 따로 변수로 두지 않고 매번 sum(queue1)를 사용해서 구했다. 그러다보니 시간 초과가 났다.
모든 함수는 시간복잡도가 존재한다는 것을 잊지 말자.
- 처음에 그냥 list로 pop(0)을 해서 풀었는데 시간초과가 발생했다.
deque
를 사용하면popleft()
를 사용할 수 있고 이는 O(1)의 시간복잡도를 가지고pop(0)
을 하게되면O(n)
의 시간 복잡도를 가진다.