<aside> 💬 lv1, 데이터 구조

두 큐의 합 같게 만들기

문제 설명

두 개의 큐가 주어집니다. 가능한 한 적은 수의 연산을 사용하여, 두 큐의 모든 원소의 합이 같아지도록 만드는 함수를 작성해주세요. 각 연산에서는 한 큐의 맨 앞 원소를 다른 큐의 맨 뒤로 옮길 수 있습니다. 두 큐의 합을 같게 만들 수 없는 경우 -1을 반환합니다.

예를 들어, 큐1이 [1, 2, 1, 2]이고 큐2가 [1, 10, 1, 2]인 경우, 2번의 연산으로 두 큐의 합을 같게 만들 수 있습니다.

제한 사항

각 큐의 길이는 1 이상 100 이하입니다.
각 큐의 원소는 1 이상 100 이하의 정수입니다.

입출력 예

입력 (큐1, 큐2)	출력 (최소 연산 횟수)
[1, 2, 1, 2], [1, 10, 1, 2]	2
[1, 1, 1, 9], [1, 1, 5, 3]	3
[1, 1, 1], [10]	-1

입출력 설명

주어진 두 큐의 모든 원소의 합을 같게 만드는 데 필요한 최소 연산 횟수를 반환합니다. 만약 불가능한 경우 -1을 반환합니다.

</aside>

😺 풀이 1. 조건문과 반복문의 활용

from collections import deque

def solution(data):
    queue1 = deque(data["queue1"]) **#1 큐 초기화 및 합계 계산**
    queue2 = deque(data["queue2"])
    sum1, sum2 = sum(queue1), sum(queue2)
    total_sum = sum1 + sum2
    operations = 0

    if total_sum % 2 != 0: **#2 홀수 합계 조건 검사**
        return -1

    while sum1 != sum2: **#3 원소 이동 및 합계 조정**
        if sum1 > sum2:
            value = queue1.popleft()
            sum1 -= value
            sum2 += value
            queue2.append(value)
        else:
            value = queue2.popleft()
            sum2 -= value
            sum1 += value
            queue1.append(value)
        operations += 1

        if operations > len(queue1) + len(queue2): **#4 연산 횟수 초과 검사**
            return -1

    return operations **#5 연산 횟수 반환**

단계별 풀이 전략

큐 초기화 및 합계 계산

두 큐 queue1, queue2를 deque로 초기화하고, 각 큐의 원소 합계 sum1, sum2를 계산합니다. 또한, 두 큐의 총 합 total_sum도 계산합니다.
홀수 합계 조건 검사

두 큐의 총 합 total_sum이 홀수인 경우, 두 큐의 합을 같게 만들 수 없으므로 즉시 -1을 반환합니다.
원소 이동 및 합계 조정

두 큐의 합계가 다를 경우, 합계가 더 큰 큐에서 원소를 제거하여 합계가 더 작은 큐의 맨 뒤로 추가합니다. 이 과정에서 각 큐의 합계를 조정하고, 수행된 연산의 횟수(operations)를 기록합니다.
연산 횟수 초과 검사

연산 횟수가 두 큐의 길이 합보다 많아질 경우, 두 큐의 합을 같게 만들 수 없는 상태임을 의미하므로 -1을 반환합니다. 이는 무한 루프에 빠지는 것을 방지합니다.
연산 횟수 반환

두 큐의 합계가 같아지면, 현재까지 수행된 연산 횟수(operations)를 반환합니다.

알아둬야 할 개념

Deque (데큐)

기본 형태: from collections import deque

개념: deque는 양방향 큐로, 양쪽 끝에서 요소를 추가하거나 제거할 수 있는 자료구조입니다. collections 모듈에서 제공됩니다.

from collections import deque

dq = deque([1, 2, 3]) # deque 생성
dq.append(4)  # dq의 맨 뒤에 4 추가 # deque([1, 2, 3, 4])
dq.appendleft(0)  # dq의 맨 앞에 0 추가 # deque([0, 1, 2, 3, 4])
dq.pop() # dq의 맨 뒤 제거 및 반환 # deque([0, 1, 2, 3])
dq.popleft()  # dq의 맨 앞 제거 및 반환 # deque([1, 2, 3])

풀이 2. 합계 동일성 검사

from collections import deque

def solution(data):
    q1 = deque(data['queue1']) **#1 큐 초기화 및 합계 계산**
    q2 = deque(data['queue2'])
    count = 0
    sum_q1 = sum(q1)
    sum_q2 = sum(q2)

    # 두 큐의 합이 홀수라면 이들을 같게 만들 수 없음
    if (sum_q1 + sum_q2) % 2 != 0: **#2 홀수 합계 조건 검사**
        return -1

    while sum_q1 != sum_q2: **#3 원소 이동 및 합계 조정**
        if sum_q1 > sum_q2: **#4 합계 동일성 검사**
            pop_q1 = q1.popleft()
            sum_q1 -= pop_q1
            sum_q2 += pop_q1
            q2.append(pop_q1)
            count += 1
        else:
            pop_q2 = q2.popleft()
            sum_q1 += pop_q2
            sum_q2 -= pop_q2
            q1.append(pop_q2)
            count += 1

        # 두 큐의 합이 홀수라면 이들을 같게 만들 수 없음
        if (sum_q1 + sum_q2) % 2 != 0: **#5 무한 루프 방지**
            return -1

    return count

단계별 풀이 전략

큐 초기화 및 합계 계산

입력 데이터로부터 두 큐 q1과 q2를 deque로 초기화하고, 각 큐의 원소 합계 sum_q1, sum_q2를 계산합니다.
홀수 합계 조건 검사

두 큐의 총 합이 홀수인 경우, 두 큐의 합을 같게 만들 수 없으므로 즉시 -1을 반환합니다.
원소 이동 및 합계 조정

두 큐의 합계가 서로 다른 경우, 합계가 더 큰 큐에서 원소를 제거하여 합계가 더 작은 큐의 맨 뒤로 추가합니다. 이 과정에서 각 큐의 합계를 적절히 조정하고, 연산 횟수 count를 증가시킵니다.