프로그래머스 / 두 큐 합 같게 만들기 / python

from collections import deque
def solution(queue1, queue2):
    answer = 0
    l = len(queue1) + len(queue2)
    q1 = deque(queue1)
    q2 = deque(queue2)
    s1 = sum(q1)
    s2 = sum(q2)
    
    while answer < 2*l:
        if s1 == s2:
            break
        elif s1 > s2:
            t = q1.popleft()
            q2.append(t)
            s1 -= t
            s2 += t
            answer += 1
        else:
            t = q2.popleft()
            q1.append(t)
            s1 += t
            s2 -= t
            answer += 1
    else:
        return -1
    
    return answer

그리디 알고리즘과 deque를 사용해서 해결한 문제

이 문제의 핵심은 두 개의 q를 같게하기 위해서 높은 쪽의 큐에서 pop 해서 작은 쪽에 append하는 것이 최적의 해라는 것이다.

이 개념만 떠울리면 쉽게 해결할 수 있다.

처음에 시간 초과가 났었는데 s1, s2 sum() 을 while문 내에서 매번 구했기 때문이다. 이 방법은 진짜 비 효율적인 방식이다. pop 할 때마다 s1, s2 값을 변경해주는 식으로 해줘야한다.