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

문제 링크

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

프로그래머스

 

접근 방식

먼저 큐에서 pop 을 할 때 pop(0) 보다 deque 의 popleft() 가 시간복잡도가 작기 때문에 deque 를 사용했다.

문제를 풀 때는 두 가지를 고려했다.

1. 정답을 찾는 방법
2. 반복문 종료 시점

예시를 보면서 Greedy 하게 합이 더 큰 큐에서 합이 작은 큐로 원소를 옮겨나가면 된다고 생각했다.

그럼 이제 언제까지 반복문을 돌아야 할지가 중요한데,

예시에서 queue1 이 [3,2,7,2] 이고 queue2 가 [4,6,5,1] 로 나와있는 걸 예시로 생각해보자.

[3,2,7,2] 가 queue2 로 가고 [4,6,5,1] 이 queue1 으로 간다면 (queue1 의 길이) * 2 만큼

작업을 수행한 것이다.

그렇다면 다시 [3,2,7,2] 가 queue1, [4,6,5,1] 이 queue2 로 간다면 (queue1 의 길이) * 4만큼

작업을 수행한 것이고, 그 때까지 합이 같은 경우가 없었다면 일치하는 경우가 없다고 생각했다.

정리하자면 정답을 찾으려면 원소 합이 큰 큐에서 합이 작은 큐로 원소를 계속 옮기고,

한 바퀴를 돌아 다시 큐의 원소들이 원상복구 될 때까지 찾지 못했다면 반복문을 종료하는 것으로

코드를 작성했다.

 

풀이 코드

from collections import deque

def solution(queue1, queue2):

    queue1 = deque(queue1)
    queue2 = deque(queue2)
    sum1 = sum(queue1)
    sum2 = sum(queue2)
    origin_len = len(queue1)
    cnt = 0

    # 두 큐 원소들을 전부 더한 값이 홀수이면 answer = -1
    if (sum1 + sum2) % 2 != 0:
        return -1

    # len(queue1)의 4배 만큼 돌렸는데도 안 되면 return -1
    while True:

        if cnt > origin_len * 4:
            return -1

        if sum1 > sum2:
            q1 = queue1.popleft()
            queue2.append(q1)
            sum1 -= q1
            sum2 += q1
        elif sum1 == sum2:
            return cnt
        else:
            q2 = queue2.popleft()
            queue1.append(q2)
            sum2 -= q2
            sum1 += q2
        cnt += 1

    return -1