[카카오 코테 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
- 최악의 경우를 *4로 안 이휴는 한 원소가 두 큐를 두 번찍 왔다갔다할 수 있으니까, 그 이상으로 갈 수도 있지만 시간 초과 문제와 최적화된 코드라면 그 이상으로 안 갈 것이다.
- while 루프 안에서 sum() 대신 +=, -= 을 해야함.
- O(N)

 

✅ 최적 코드

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

 

 ➰ 디버깅 코드

from collections import deque

def solution(queue1, queue2):
    queue1 = deque(queue1)
    queue2 = deque(queue2)
    sum1 = sum(queue1)
    sum2 = sum(queue2)
    tot = sum1 + sum2
    max_loop = len(queue1) * 3
    count = 0

    print(f"초기 상태:")
    print(f"  queue1: {list(queue1)} | sum1: {sum1}")
    print(f"  queue2: {list(queue2)} | sum2: {sum2}")
    print("--------------------------------------------------")

    if sum1 == sum2:
        return 0

    while count < max_loop:
        print(f"[{count+1}번째 이동]")

        if sum1 > tot // 2:
            cur = queue1.popleft()
            sum1 -= cur
            queue2.append(cur)
            sum2 += cur
            print(f"  queue1 → queue2: {cur}")
        else:
            cur = queue2.popleft()
            sum2 -= cur
            queue1.append(cur)
            sum1 += cur
            print(f"  queue2 → queue1: {cur}")

        print(f"  queue1: {list(queue1)} | sum1: {sum1}")
        print(f"  queue2: {list(queue2)} | sum2: {sum2}")
        print("--------------------------------------------------")

        count += 1
        if sum1 == sum2:
            print(f"✅ 균형 달성! 이동 횟수: {count}")
            return count

    print("❌ 최대 이동 횟수를 초과하여 균형 불가")
    return -1

 

🐥 내 풀이

from collections import deque

def solution(queue1, queue2):
    queue = deque()
    queue1 = deque(queue1)
    queue2 = deque(queue2)
    sum1 = sum(queue1)
    sum2 = sum(queue2)
    max_loop = len(queue1)*3
    tot = sum(queue1) + sum(queue2)
    count = 0
    
    if sum(queue1) == sum(queue2):
        return 0
    
    while count < max_loop:
        if sum1 > tot//2:
            cur = queue1.popleft()
            sum1 -= cur
            queue2.append(cur)
            sum2 += cur
            count += 1
        else:
            cur = queue2.popleft()
            sum2 -= cur
            queue1.append(cur)
            sum1 += cur
            count += 1
            
        if sum1 == sum2:
            return count
                
    return -1

 

 

😃 추천 강의

38군데 합격 비법, 2025 코딩테스트 필수 알고리즘 강의 | 딩코딩코 - 인프런

 

기출로 대비하는 개발자 전공면접 [CS 완전정복] 강의 | 개발남노씨 - 인프런