LV 2: 두 큐 합 같게 만들기

문제 링크

LV 2: 두 큐 합 같게 만들기

구현 방식

• while문을 돌면서, 1)queue1의 총합이 queue2의 총합보다 크다면 queue1에서 popleft, queue2에 append. 2)queue2의 총합이 queue1의 총합보다 크다면 queue2에서 popleft, queue1에 append. 3)만약 두 큐의 총합이 같다면 count를 return

• 시간 복잡도를 줄이기 위해, 매 반복마다 sum()연산을 사용하지 않고 그냥 sum_queue1, sum_queue2에서 더하고 빼는 형식으로 두개의 변수로 처리해주었다

• 유의미한 pop, insert 연산은 count가 큐의 길이 * 4 이하일 때까지 이므로, 이를 넘어가면 바로 -1을 return 해주도록 하였다

• 또한, 두 큐의 합이 홀수이면 두 큐의 합을 같게 만드는게 불가능하므로 바로 -1을 return 해주는 부분을 먼저 구현해주었다

코드

from collections import deque

def solution(queue1, queue2):
    if (sum(queue1) + sum(queue2)) % 2 == 1: return -1
    
    N = len(queue1)
    queue1 = deque(queue1); queue2 = deque(queue2)
    
    count = 0; sum_queue1 = sum(list(queue1)); sum_queue2 = sum(list(queue2))
    while True:
        if count > N*4: return -1
        if sum_queue1 == sum_queue2: return count
        elif sum_queue1 > sum_queue2:
            one = queue1.popleft(); queue2.append(one)
            sum_queue1 -= one; sum_queue2 += one
            count += 1
        elif sum_queue1 < sum_queue2:
            two = queue2.popleft(); queue1.append(two)
            sum_queue2 -= two; sum_queue1 += two
            count += 1