[카카오 코테 2022 | python] 두 큐 합 같게 만들기

• 문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/118667
• Level2

 

Q1) 문제를 어떻게 이해했나요?
A1) 입력: 두 개의 같은 길이의 큐
출력: 각 큐의 합이 같아질 때까지의 최소 작업 횟수
조건: 큐는 FIFO 구조, 어떤 방식으로도 합을 같게 못 맞추면 -1 반환

Q2) 문제를 어떻게 풀 예정인가요?
A2) deque로 큐 구현 → sum(queue1)이 목표의 절반 크기보다 크면 queue1에서 꺼내서 queue2로 이동, 반대도 마찬가지
두 큐의 합이 같아 지는 순간 return

 

✅ 최적 코드

from collections import deque

def solution(queue1, queue2):
    q1 = deque(queue1)
    q2 = deque(queue2)
    
    sum1 = sum(q1)
    sum2 = sum(q2)
    total = sum1 + sum2
    
    if total % 2 != 0:
        return -1  # 합이 홀수면 나눌 수 없음

    target = total // 2
    max_ops = len(queue1) * 4  # 최악의 경우: 양방향 이동 반복
    count = 0

    while count <= max_ops:
        if sum1 == target:
            return count
        if sum1 > target:
            # q1에서 꺼내서 q2에 넣음
            num = q1.popleft()
            sum1 -= num
            q2.append(num)
            sum2 += num
        else:
            # q2에서 꺼내서 q1에 넣음
            num = q2.popleft()
            sum2 -= num
            q1.append(num)
            sum1 += num
        count += 1
    
    return -1  # 제한 횟수 넘었으면 -1