프로그래머스 Level 2 | 두 큐 합 같게 만들기 | Python

https://school.programmers.co.kr/learn/courses/30/lessons/118667

문제 파악

숫자 원소가 들어있는 큐가 두개 주어졌을 때,
popleft(), push() 연산을 이용하여 두 큐의 원소의 합을 동일하게 만드는 작업의 최소횟수를 return하는 문제이다.

어떤 방법으로도 큐 원소 합을 같게 만들 수 없는 경우는 -1을 return 한다.

해결 아이디어

어떻게 풀 수 있을까?

q1과 q2 원소의 합을 비교하여 더 작은 쪽에서 큰 쪽으로 popleft()&push() 연산을 해주고, cnt를 1 올려주는 것을 반복한다.

어떤 방법으로도 각 큐의 원소 합을 같게 만들 수 없는 경우라는 것은 어떻게 알까?

불가능 판단 기준

1. 전체 합이 홀수면 무조건 불가능
   total = sum(q1) + sum(q2) 가 홀수 → -1.

2. 어느 한 원소가 목표 합(= total/2)보다 크면 불가능
   max(q1+q2) > total//2 → -1.

3. 두 포인터/슬라이딩 윈도우로 돌렸는데 상한 횟수를 초과하면 불가능
   큐 두 개를 이어붙인 배열 arr = q1 + q2에서,
   i(왼쪽), j(오른쪽) 포인터를 움직이며 현재 구간합을 sum(q1)로 시작해 target = total//2를 맞춰간다.
   이때 한 번의 포인터 이동 = 실제로 한 번 popleft & push 한 것과 동일.
   포인터는 각각 최대 len(arr)번(= 원형 한 바퀴)까지만 의미가 있으니,
   연산 상한을 2 * len(arr) (즉, 각 포인터 한 바퀴씩)으로 잡고 초과 시 -1 로 두면 된다.

해답 및 풀이

from collections import deque

def solution(q1, q2):
    q1, q2 = deque(q1), deque(q2)
    s1, s2 = sum(q1), sum(q2)
    total = s1 + s2
    
    # 전체 합이 홀수면 무조건 불가능
    if total % 2: 
        return -1
       
    # 어느 한 원소가 목표 합(= total/2)보다 크면 불가능   
    target = total // 2
    if max(q1 + q2) > target:
        return -1

    limit = 2 * (len(q1) + len(q2))  # 연산 상한
    cnt = 0
    
    while cnt <= limit and s1 != target:
        if s1 < target:
            # q2의 앞을 q1 뒤로
            if not q2: return -1
            x = q2.popleft()
            q1.append(x)
            s1 += x
            s2 -= x
        else:
            # s1 > target: q1의 앞을 q2 뒤로
            if not q1: return -1
            x = q1.popleft()
            q2.append(x)
            s1 -= x
            s2 += x
        cnt += 1

    return cnt if s1 == target else -1