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

문제

문제 설명

길이가 같은 두 개의 큐가 주어집니다. 하나의 큐를 골라 원소를 추출(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 해주세요.

 

입력 & 출력

입출력 예

queue1 queue2 result

[3, 2, 7, 2]	[4, 6, 5, 1]	2
[1, 2, 1, 2]	[1, 10, 1, 2]	7
[1, 1]	[1, 5]	-1

 

풀이 과정

코드 2로 deque를 이용한 방식으로 해결하려고 하였는데 제출 시 통과 못하는 부분이 많아서 다른 방법으로 구현하였다.

1. 코드 2에서는 solution함수 외부에 새로운 함수를 만들어서 count 되는 숫자를 리턴하는 방식으로 구상하였었지만 1번 내용은 for문과 조건문의 조합을 구상

2. 처음에 deque를 이용하여 자료형을 선언하여서 popleft를 사용할 수 있게 만들어준다.

3. queue1과 queue2의 합이 같은지를 판별하는 조건문을 사용하도록 하고 각각 queue1이 더 클 때와 queue2가 더 클 때의 경우에 따라서 팝 하는 큐를 반전시켜주고 같을 경우에는 i의 숫자를 반환 만약 for문이 종료될 때까지도 같아지지 않는 다면 -1을 반환하여서 문제의 예외 처리도 해줄 수 있도록 한다.

 

코드

코드 1

from collections import deque


def solution(queue1, queue2):
    queue_1 = deque(queue1)
    queue_2 = deque(queue2)
    s_1 = sum(queue_1)
    s_2 = sum(queue_2)

    for i in range(len(queue1) * 3):
        if s_1 == s_2:
            return i
        if s_1 > s_2:
            num = queue_1.popleft()
            queue_2.append(num)
            s_1 -= num
            s_2 += num
        else:
            num = queue_2.popleft()
            queue_1.append(num)
            s_2 -= num
            s_1 += num
    return -1

코드 2

from collections import deque


def push_and_pop(first, second, count, limit):
    if sum(first) < sum(second):
        first.append(second.popleft())
    else:
        second.append(first.popleft())

    count += 1
    if count > limit:
        count = -1
    return count


def solution(queue1, queue2):
    count = 0

    queue1 = deque(queue1)
    queue2 = deque(queue2)

    limit = len(queue1) + len(queue2)

    while sum(queue1) != sum(queue2):
        count = push_and_pop(queue1, queue2, count, limit)
        if count == -1:
            break

    return count