두 큐 합 같게 만들기

문제 파악

주어진 두 큐의 합을 동일하게 만들기 위해 큐의 요소를 옮기는 최소 횟수를 구하는 문제이다. 만약 두 큐의 합을 동일하게 만들 수 없다면 -1을 반환한다.

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

접근 방법

1. 두 큐의 합을 구하여 목표값을 설정
2. 두 큐의 합이 목표값과 같아질 때까지 요소를 이동
3. 이동된 횟수를 반환(만약 두 큐의 합을 동일하게 만들 수 없다면 -1을 반환)

코드 구현

from collections import deque

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

    deq1 = deque(queue1)
    deq2 = deque(queue2)

    cnt = 0
    sum_queue1 = sum(deq1)
    sum_queue2 = sum(deq2)

    for _ in range(len(deq1) * 3):
        if sum_queue1 > target:
            temp = deq1.popleft()
            deq2.append(temp)
            sum_queue1 -= temp
            sum_queue2 += temp
            cnt += 1
        elif sum_queue1 < target:
            temp = deq2.popleft()
            deq1.append(temp)
            sum_queue1 += temp
            sum_queue2 -= temp
            cnt += 1
        else:
            return cnt

    return -1

배우게 된 점

처음에는 각 반복마다 sum() 함수를 사용하여 각 큐의 합을 다시 계산하는 방식으로 접근했다. 그러나 이 방식은 중복 계산으로 인해서 시간초과 케이스들을 접했습니다. sum() 함수는 리스트의 모든 요소를 순회하여 합을 계산하기 때문에 시간복잡도가 O(n)입니다. 따라서 매 반복마다 sum() 함수를 호출하면 반복된 계산으로 인해 전체적인 시간복잡도가 증가하게 됩니다. 이를 해결하기 위해 처음에만 두 큐의 합을 계산하고, 이후 반복문에서는 이동된 요소의 값을 각각 더하고 빼는 방식을 채택했습니다. 이를 통해 반복된 계산을 줄임으로써 시간복잡도를 크게 개선할 수 있었습니다.