Algorithm
프로그래머스
Python
두 큐의 합 같게 만들기

두 큐의 합 같게 만들기

문제 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

배운점

  1. 합을 따로 변수로 두지 않고 매번 sum(queue1)를 사용해서 구했다. 그러다보니 시간 초과가 났다. 모든 함수는 시간복잡도가 존재한다는 것을 잊지 말자.
  2. 처음에 그냥 list로 pop(0)을 해서 풀었는데 시간초과가 발생했다. deque를 사용하면 popleft()를 사용할 수 있고 이는 O(1)의 시간복잡도를 가지고 pop(0)을 하게되면 O(n)의 시간 복잡도를 가진다.