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

[문제 풀이]

• 두 큐의 합이 같게 되려면 모든 원소의 평균이 정수여야 하며, 각 큐의 합이 평균과 동일하게 만들어주면 됩니다.
• 문제에 대한 설명과 같이, 시간복잡도을 낮추고 큐의 특성을 활용하기 위해 deque()를 사용했으며, 원소의 합이 큰 쪽에서 작은 쪽으로 원소를 보내주도록 구현하였습니다.
• 이때 매번 큐의 합을 구해주는 것이 아닌 구해놓은 합에 대하여 +- 연산을 통해 시간 복잡도를 낮췄습니다.
• 마지막으로 두 개의 큐가 비지 않고 큐의 길이 * 2번 만큼 이동하게 된다면 원 상태가 되므로 해당 조건을 추가하였습니다.

 

[풀이 코드]

from collections import deque


def solution(queue1, queue2):
    answer = 0
    sum1 = sum(queue1)
    sum2 = sum(queue2)
    s = (sum1 + sum2) / 2

    if s - int(s) > 0 or max(queue1) > int(s) or max(queue2) > int(s):
        return -1

    dq1 = deque(queue1)
    dq2 = deque(queue2)

    while dq1 and dq2 and sum1 != sum2 and answer <= 600000:
        if sum1 < sum2:
            v = dq2.popleft()
            dq1.append(v)

            sum1 += v
            sum2 -= v
        else:
            v = dq1.popleft()
            dq2.append(v)

            sum1 -= v
            sum2 += v
        answer += 1

    return answer if sum1 == sum2 else -1