[프로그래머스] 두 큐 합 같게 만들기 파이썬 정답 코드

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

프로그래머스

---

1. 접근 방식

• 각 큐의 합이 더 작은 큐에 원소를 추가하는 작업을 반복한다.

q1과 q2가 있을 때 각 큐의 원소 합을 같게 만들어가는 과정은 위와 같다. q1과 q2 각 합을 비교하여, 합이 더 작은 쪽에 큰 큐의 첫 번째 원소를 더해주는 작업이 반복된다. 그러다가 두 큐의 원소 합이 똑같아지면, 반복 작업을 종료하면 된다. 위 그림의 경우 2번의 작업으로 각 큐의 원소 합이 같아졌다.

 

• 각 큐의 원소 합을 동일하게 만들 수 없는 경우는 무엇일까?
  • 두 큐의 원소 합이 홀수일 경우. Ex) q1 = [ 1, 2 ], q2 = [ 4, 6 ]
  • pop과 insert를 반복하다가, 어느 순간 처음과 똑같은 큐로 되돌아갈 경우

첫 번째, 홀수 케이스는 ( sum(q1) + sum(q2) ) % 2를 통해 쉽게 처리할 수 있다.

두 번째는 각 큐의 최대 길이가 30만이므로, 최소 pop과 insert 작업이 60만 번 이상 반복된다면 결국 처음과 똑같은 큐로 되돌아간다는 의미이다. 즉, 각 원소 합이 똑같아지는 큐를 만들 수 없다는 것이므로 -1이 반환되어야 한다.

 

• 큐의 최대 길이가 30만으로 크기 때문에 최대한 실행 시간을 줄이자.

큐의 첫 번째 원소를 pop하는 시간을 줄이고자 deque 모듈을 사용한다. 일반 리스트에서 pop(0)은 O(n) 시간 복잡도를 가지지만, 동일한 기능을 하는 deque의 popleft( )는 O(1) 시간 복잡도를 갖는다.

while sum(q1) != sum(q2):
    if not q1 or not q2:
        answer = -1
        break
            
    if sum(q1) < sum(q2):
        q1.append(q2.popleft())
    else:
        q2.append(q1.popleft())
        
    answer += 1

또한 pop과 insert 반복 작업에서 sum( ) 함수의 사용을 최소화하였다. 위 코드는 sum( ) 함수를 많이 사용하고 있는데, sum( )은 O(n) 시간 복잡도를 갖는다. 따라서 사용을 최소화하기 위해 sum( ) 함수를 초기 q1과 q2의 각 원소 합을 구할 때만 사용하고, 반복문 내에서는 기존 sum1, sum2에 직접 원소 값을 더하고 빼는 것으로 처리했다.

 

 

2. 정답 코드

def solution(queue1, queue2):
    from collections import deque
    
    q1, q2 = deque(queue1), deque(queue2)
    sum1, sum2 = sum(q1), sum(q2)
    
    if (sum1 + sum2) % 2: # 총 합이 홀수라면 각 큐가 똑같은 합을 가질 수 없다.
        return -1
    
    answer, count = 0, 0
    while sum1 != sum2:
        count += 1
        
        if not q1 or not q2 or count > 600000:
            answer = -1
            break
            
        if sum1 < sum2:
            e = q2.popleft()
            q1.append(e)
            sum1 += e
            sum2 -= e
        else:
            e = q1.popleft()
            q2.append(e)
            sum1 -= e
            sum2 += e
        
        answer += 1

    return answer