[Python] 프로그래머스 118667. 두큐합같게만들기 (Lv.2)

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

프로그래머스

 

두 큐의 합을 같게 만드는 문제입니다.

그리디 하게 합이 더 큰 쪽의 큐에서 수를 빼서 작은 쪽으로 넣으면 되는데, 이유는 조금만 생각해봐도 떠올릴 수 있습니다.

(큐의 선입선출 구조를 생각하시면 왜 그리디하게 풀이해서 정답이 나오는지 알 수 있습니다.)

 

입력된 리스트를 두개의 큐에 (Python의 경우 deque) 담고 그리디 하게 값을 빼고 넣어주며 같은 값이 되게 해 주면 됩니다.

실행시간을 단축시키는 가지치기가 몇개 가능한데, 우선 두 큐의 합을 더한 값이 홀수면 어떤 방법을 써도 같게 만들 수가 없습니다. 3을 정수로 2등분 시키는 게 불가능하듯이요.

2로 나눈 나머지가 0이 아니면 -1을 리턴하시면 됩니다. 그리고 큐의 합을 매번 구하지 않도록 초기 상태에서 합을 미리 구해놓은 다음, 옮기는 수만 합에서 직접 빼고 더해주면 매번 큐의 합을 구하는 것보다 빠르게 동작할 수 있습니다.

 

from collections import deque


def solution(queue1, queue2):
    left = sum(queue1)
    lqueue = deque(queue1)
    right = sum(queue2)
    rqueue = deque(queue2)
    limit = 2 * (len(queue1) + len(queue2))
    count = 0

    if (left + right) % 2 == 1:
        return -1

    while count < limit:

        if left == right:
            return count

        if left < right:
            gap = rqueue.popleft()
            left += gap
            right -= gap
            lqueue.append(gap)
        else:
            gap = lqueue.popleft()
            right += gap
            left -= gap
            rqueue.append(gap)

        count += 1
    return -1


print(solution([3, 2, 7, 2], [4, 6, 5, 1]))