[코테 - py] 두 큐 합 같게 만들기

https://school.programmers.co.kr/learn/courses/30/lessons/118667?language=python3

프로그래머스

이번에는 큐를 이용한 문제였다.

여기서 시간복잡도를 고려하여 코드를 짜는게 어려웠다.

처음 시간초과가 발생한 이유는 sum 때문이었는데, sum은 시간복잡도가 O(n)이기 때문에 내가 처음 작성한 것은 시간복잡도가 초과할 수 밖에 없는 구조였다.

이를 고려하기 위해 계속 업데이트한 큐의 sum을 구하는게 아니라 각각 처음 구한 합에서 popleft() 한값만을 빼주고, append한 값을 더해주는 식으로 구성했다.

from collections import deque
"""
시간 초과를 막기 위해, 각 큐에서 더하고 뺀값만 합쳐준다.
sum은 O(n)의 시간복잡도를 가지기 때문에 시간초과!
"""
def solution(queue1, queue2):
    # 큐로 바꿈
    queue1 = deque(queue1)
    queue2 = deque(queue2)
    # 합을 비교하기 위해 각각 합을 구한다.
    sum1 = sum(queue1)
    sum2 = sum(queue2)
    # 합을 같게 만들기 위한 작업의 최소 횟수
    count = 0

    # 큐의 최대의 길이인 300000만큼 실행 -> 불가하면 -1 반환
    for _ in range(300000):
        # 합이 같으면 최소 횟수 반환
        if sum1 == sum2:
            return count
        # queue1의 합이 더 크다면, queue1의 원소 추출
        if sum1 > sum2:
            a = queue1.popleft()
            queue2.append(a)              
            sum1 -= a
            sum2 += a
        # queue2의 합이 더 크다면, queue2의 원소 추출 
        elif sum1 < sum2:
            a = queue2.popleft()
            queue1.append(a)        
            sum1 += a
            sum2 -= a
        # 교환 후 횟수 증가
        count += 1
    return -1