[프로그래머스][Python] 두 큐 합 같게 만들기

프로그래머스

 

코드

from collections import deque
def solution(queue1, queue2):
    queue1 = deque(queue1)
    queue2 = deque(queue2)
    sum1 = sum(queue1)
    sum2 = sum(queue2)
    cnt = 0

    l = len(queue1)
    for _ in range(l*4):
        if sum1 < sum2:
            num = queue2.popleft()
            queue1.append(num)
            sum1 += num
            sum2 -= num
            cnt += 1
        elif sum1 > sum2:
            num = queue1.popleft()
            queue2.append(num)
            sum1 -= num
            sum2 += num
            cnt += 1
        else:
            return cnt
            
    return -1

 

 

설명

처음에 for문에서 sum을 이용하여 큐의 합을 구했더니 시간 초과가 났다.

파이썬에서 sum 의 시간 복잡도는 O(n)이기 때문에 계속 반복하는 것보다 변수에 값을 저장해서 비교하는 것이 훨씬 빠르다.

deque를 사용한 이유도 그냥 pop(0)을 하는 것보다 deque로 바꿔서 popleft()를 하는 것이 더 빠르기 때문이다.

pop()은 한 번 진행한 후에 한 칸씩 당겨야 하기 때문에 O(n)의 시간복잡도를 가진다.

 

가장 적게 움직이는 방법은 큐에 들어있는 숫자의 총합이 더 큰 쪽에서 작은 쪽으로 옮기는 것이다