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

 카카오 인턴쉽 문제답게 힘들었다. 코드를 보면서 설명하겠다.

<문제>

https://school.programmers.co.kr/learn/courses/30/lessons/118667?language=python3

프로그래머스

 

---

<소스코드>

<시간 초과 코드>

from collections import deque

def solution(queue1, queue2):
    q1 = deque(queue1)
    q2 = deque(queue2)
    
    total = sum(q1) + sum(q2)
    goal = total // 2
    
    for x in q1:
        if x > goal: return -1
    for x in q2:
        if x > goal: return -1
    cnt = 0
    
    while True:
        if sum(q1) == goal:
            return cnt
        if len(q1) == 0 or len(q2) == 0:
            return -1
        
        cnt += 1
        if sum(q1) < sum(q2):
            q1.append(q2.popleft())
        elif sum(q1) > sum(q2):
            q2.append(q1.popleft())

<통과 코드>

from collections import deque

def solution(queue1, queue2):
    q1 = deque(queue1)
    q2 = deque(queue2)
    sum1 = sum(q1)
    sum2 = sum(q2)
    
    total = sum1 + sum2
    goal = total // 2
    cnt = 0
    
    while cnt < 2*max(len(q1), len(q2))+1:
        if sum1 == goal:
            return cnt
        
        if sum1 < goal:
            value = q2.popleft()
            sum1 += value
            q1.append(value)
        elif sum1 > goal:
            value = q1.popleft()
            sum1 -= value
            q2.append(value)
            
        cnt += 1
        
    return -1

 

일단 시간 초과한 코드와 통과한 코드의 문제 풀이 방식은 같다.

 

두 큐의 합을 지속적으로 비교를 하며, 합이 큰 큐가 작은 큐에게 자신의 원소를 하나 떼어 주는 형식으로 진행을 하게 된다.

다만, 다른 점은

while문을 어느 한쪽의 큐가 빌 때까지 진행을 하였고 VS 횟수를 긴 길이의 큐의 2배 한 것까지 제한을 했다. 

그리고, while문 내에서 sum 함수를 지속적으로 사용했고 VS sum1을 기준으로 중간값을 가지고 크고 작고를 비교했다.

 

이 두 가지 차이가 통과와 불통을 가르는 중요한 포인트가 되었는데

첫 번째의 경우 2배 이상으로 기준을 잡은 이유는 그 이상으로 진행을 할 경우 이미 큐끼리 값들이 뒤바뀌고도 남았을 것이라는 추론에 기인하였다. 

 

두 번째의 경우는 매번 sum함수를 이용하는 건 쉽게 예상할 수 있듯이 시간 낭비가 심할 것이고, 한쪽만 비교하면서 중간값을 초월했는지만 파악하면 다른 쪽보다 작은 지 큰 지 구분이 가기 때문에 아래 코드처럼 진행을 하였다.

 

이런 부분도 아끼고 아껴야 통과할 수 있는 무서운 문제였다.