프로그래머스 - KAKAO 두 큐 합 같게 만들기 [파이썬]

문제 링크 : https://school.programmers.co.kr/learn/courses/30/lessons/118667

프로그래머스

 

문제 설명 : 

길이가 같은 두 개의 큐가 주어집니다. 하나의 큐를 골라 원소를 추출(pop)하고, 추출된 원소를 다른 큐에 집어넣는(insert) 작업을 통해 각 큐의 원소 합이 같도록 만들려고 합니다. 이때 필요한 작업의 최소 횟수를 구하고자 합니다. 한 번의 pop과 한 번의 insert를 합쳐서 작업을 1회 수행한 것으로 간주합니다.

 

큐는 먼저 집어넣은 원소가 먼저 나오는 구조입니다. 이 문제에서는 큐를 배열로 표현하며, 원소가 배열 앞쪽에 있을수록 먼저 집어넣은 원소임을 의미합니다. 즉, pop을 하면 배열의 첫 번째 원소가 추출되며, insert를 하면 배열의 끝에 원소가 추가됩니다. 예를 들어 큐 [1, 2, 3, 4]가 주어졌을 때, pop을 하면 맨 앞에 있는 원소 1이 추출되어 [2, 3, 4]가 되며, 이어서 5를 insert하면 [2, 3, 4, 5]가 됩니다.

 

다음은 두 큐를 나타내는 예시입니다.

queue1 = [3, 2, 7, 2]
queue2 = [4, 6, 5, 1]

두 큐에 담긴 모든 원소의 합은 30입니다. 따라서, 각 큐의 합을 15로 만들어야 합니다. 예를 들어, 다음과 같이 2가지 방법이 있습니다.

1. queue2의 4, 6, 5를 순서대로 추출하여 queue1에 추가한 뒤, queue1의 3, 2, 7, 2를 순서대로 추출하여 queue2에 추가합니다. 그 결과 queue1은 [4, 6, 5], queue2는 [1, 3, 2, 7, 2]가 되며, 각 큐의 원소 합은 15로 같습니다. 이 방법은 작업을 7번 수행합니다.
2. queue1에서 3을 추출하여 queue2에 추가합니다. 그리고 queue2에서 4를 추출하여 queue1에 추가합니다. 그 결과 queue1은 [2, 7, 2, 4], queue2는 [6, 5, 1, 3]가 되며, 각 큐의 원소 합은 15로 같습니다. 이 방법은 작업을 2번만 수행하며, 이보다 적은 횟수로 목표를 달성할 수 없습니다.

따라서 각 큐의 원소 합을 같게 만들기 위해 필요한 작업의 최소 횟수는 2입니다.

길이가 같은 두 개의 큐를 나타내는 정수 배열 queue1, queue2가 매개변수로 주어집니다. 각 큐의 원소 합을 같게 만들기 위해 필요한 작업의 최소 횟수를 return 하도록 solution 함수를 완성해주세요. 단, 어떤 방법으로도 각 큐의 원소 합을 같게 만들 수 없는 경우, -1을 return 해주세요.

 

정답 코드 

from collections import deque


def solution(queue1, queue2):
    q1, q2 = deque(queue1), deque(queue2)
    s1, s2 = sum(q1), sum(q2)
    count, max_count = 0, len(q1) * 3

    if s1 == s2:
        return 0
    elif (s1 + s2) % 2 == 1:  # 같아질 수 없음
        return -1

    while True:
        if s1 > s2:
            i = q1.popleft()
            q2.append(i)
            s1 -= i
            s2 += i
            count += 1
        elif s2 > s1:
            i = q2.popleft()
            q1.append(i)
            s2 -= i
            s1 += i
            count += 1
        else:
            break
        if count == max_count:
            return -1

    return count

우선 queue 이기 때문에 deque를 잘 이용하면 잘 해결될 것이라 생각했다.

하지만, 풀고나서는 큐는 그저 문제를 위한 요소라고 밖에 안들었다.

 

처음엔 투포인터로 접근하고자 했지만,  두 큐의 길이가 같다는 점과 길이가 같은 큐 내부의 합이 같아야한다는 점에 집중하였다. 

또한 두 큐(list)를 조작하면서 언제 비교를 더 이상하지 말아야하는 지를 먼저 정의 내려야했다. 

하나의 큐의 요소 개수가 다른 큐에 전체 이동했을 때
그리고 다시 원상태로 돌아오는 상황(두 큐의 원소가 서로 switch 되었다고 가정)으로 생각하면 max 횟수는 큐 길이 * 3 으로 정의내릴 수 있었다.  

 

그리고 나머지는 문제에 쓰인 대로 작성해나갔다.