[프로그래머스] 두 큐 합 같게 만들기 (python)

⏱️ 소요시간

1시간. (전략은 쉽게 떠올렸으나 반복 탈출 조건을 생각하는게 까다로웠다)

📚 문제 요약

[프로그래머스] 두 큐 합 같게 만들기
두 큐가 주어지고, 두 큐의 합이 같도록 만들 수 있는 최소 횟수 리턴 (불가한 경우 -1 리턴)

📑 풀이 요약

주어진 두 큐의 합을 먼저 구하고, 합계가 큰 큐에서 원소를 dequeue하여 합계가 작은 큐에 해당 원소를 enqueue하는 방식.

두 큐 합이 같도록 만드는게 목표이다. 목표값은 두 큐 합을 구한 뒤에 2로 나눠주면 된다. (ex. queue1 의 합계는 10, queue2의 합계는 12라면 둘 다 22/2 = 11 이 되도록 원소를 뺐다가 넣다가 하면 됨)

목표값이 2로 나누어 떨어지지 않는다면? 원소를 빼고 넣을 것도 없이 바로 불가하다는 것을 알 수 있다.

그렇다면 계속 원소를 swap해도 불가한 경우는 어떨까? 예를 들어 [1,10], [3, 4] 와 같은 케이스이다. 혹은 [1,2,3], [10, 20, 60]과 같은 케이스다. 직접 큐에서 원소를 뺐다 넣었다 하면서 동작 과정을 살펴보자.

일반화해보면 두 큐의 길이가 각각 n, n이라고 하면 (두 큐의 길이는 같다고 문제에 나와있음) 4n번만큼 해봤는데도 목표에 도달하지 않는다면 이는 두 큐의 합이 같도록 만들 수 없음을 의미하므로 -1을 리턴한다.

💻 전체 코드

from collections import deque
def solution(queue1, queue2):
    queue1 = deque(queue1)
    queue2 = deque(queue2)
    tot1 = sum(queue1)
    tot2 = sum(queue2)
    limit = 4 * len(queue1)
    if (tot1+tot2)%2 != 0:
        return -1
    cnt = 0
    while cnt < limit:
        if tot1 == tot2:
            return cnt

        if tot1 > tot2:
            a = queue1.popleft()
            queue2.append(a)
            tot2 += a
            tot1 -= a
        elif tot1 < tot2:
            a = queue2.popleft()
            queue1.append(a)
            tot1 += a
            tot2 -= a
        cnt += 1
    return -1

💡 새롭게 알게 된 점

큐 자료구조를 python에서 사용하고싶다면
from collections import deque
길이가 N인 리스트에서 idx 0 번의 값을 pop하려면 O(N)만큼 시간이 소요되지만, deque를 사용하여 idx 0번의 값을 pop하게 된다면 O(1)만큼 시간이 소요된다! (deque가 내부적으로 양방향 연결리스트로 구현되어있음)