프로그래머스 - 두 큐 합 같게 만들기 (2022 KAKAO TECH INTERNSHIP) / Level 2 / Python

문제 📋

코딩테스트 연습 - 두 큐 합 같게 만들기

풀이 📝

from collections import deque


def solution(queue1, queue2):
    answer = 0
    target = (sum(queue1) + sum(queue2)) // 2

    q1 = deque(queue1)
    q2 = deque(queue2)

    sum_val = sum(q1)

    while sum_val != target:

        if sum_val < target:
            item = q2.popleft()
            q1.append(item)
            sum_val += item
        else:
            item = q1.popleft()
            sum_val -= item

        if not q2:
            return -1

        answer += 1

    return answer

조금만 고민해보면 어렵지 않은 문제이다.
이 문제는 큐 하나로 대상을 국한 시키면 정말 쉬운 로직이 된다.
먼저 target을 (sum(queue1) + sum(queue2)) // 2 로 정해주고
하나의 큐을 정해서 해당 큐의 합이 target이 되도록 하는 것이다.

target보다 크면 pop해서 버리면 되고 부족하면 queue2에서 가져오면 된다.
queue2에서 다 가져와도 target을 못만들었다면 더이상 방법이 없기 때문에 -1을 리턴하면 된다.

다만 큐의 길이가 최대 300,000이기 때문에 시간복잡도 측면에서 고려할 부분이 있다.
먼저 pop과 append를 상수 시간내에 할 수 있도록 deque을 사용했으며
sum() 함수도 O(n)의 시간복잡도를 가지기 때문에 한번만 호출하고 반복문 내에서는 해당 변수를 관리해주면서 사용했다.