[프로그래머스] 두 큐 합 같게 만들기_Python level2(스택/큐)

🔒 문제

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 해주세요.

---

제한사항

• 1 ≤ queue1의 길이 = queue2의 길이 ≤ 300,000
• 1 ≤ queue1의 원소, queue2의 원소 ≤ 109
• 주의: 언어에 따라 합 계산 과정 중 산술 오버플로우 발생 가능성이 있으므로 long type 고려가 필요합니다.

---

입출력 예

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

---

입출력 예 설명

입출력 예 #1

문제 예시와 같습니다.

입출력 예 #2

두 큐에 담긴 모든 원소의 합은 20입니다. 따라서, 각 큐의 합을 10으로 만들어야 합니다. queue2에서 1, 10을 순서대로 추출하여 queue1에 추가하고, queue1에서 1, 2, 1, 2와 1(queue2으로부터 받은 원소)을 순서대로 추출하여 queue2에 추가합니다. 그 결과 queue1은 [10], queue2는 [1, 2, 1, 2, 1, 2, 1]가 되며, 각 큐의 원소 합은 10으로 같습니다. 이때 작업 횟수는 7회이며, 이보다 적은 횟수로 목표를 달성하는 방법은 없습니다. 따라서 7를 return 합니다.

입출력 예 #3

어떤 방법을 쓰더라도 각 큐의 원소 합을 같게 만들 수 없습니다. 따라서 -1을 return 합니다.

 

---

🔓 풀이

🔑 문제 해결 / 코드

from collections import deque


def solution(queue1, queue2):
    answer = 0
    queue1 = deque(queue1)
    queue2 = deque(queue2)
    limit = (len(queue1)) * 4
    tot1 = sum(queue1)
    tot2 = sum(queue2)
    total = tot1 + tot2

    if total % 2 != 0:
        return -1

    while True:
        if tot1 > tot2:
            target = queue1.popleft()
            queue2.append(target)
            tot1 -= target
            tot2 += target
            answer += 1
        elif tot1 < tot2:
            target = queue2.popleft()
            queue1.append(target)
            tot1 += target
            tot2 -= target
            answer += 1
        else:
            break
        if answer == limit:
            answer = -1
            break
    return answer

---

🍀 Story

조건 point

• queue1과 queue2의 길이는 같다.
• queue1과 queue2의 합을 같게 만들어야 한다.

해결 point

• 최적의 해를 찾아가는 방법 찾기
• 반복문 탈출 조건 찾기

이번 문제는 파라미터로 큐를 받는 큐 자료형을 사용하는 문제이며 큐 자료형의 특성을 사용하기 위해 deque을 사용했다.

list의 pop(0)를 사용하면 시간 복잡도가 상승해서 시간 초과의 위험이 있기에 deque의 popleft()를 사용했다.

 

최적의 해를 찾는 조건은 예시의 문제를 생각해보며 찾을 수 있었다.

문제에도 설명되어 있는 1번 예시를 보면(queue1 = [3, 2, 7, 2], queue2 = [4, 6, 5, 1]) 최적의 해인 2가 되기 위해서는 queue2의 4를 queue1로 옮기고 queue1의 3을 queue2로 옮기면 양쪽의 합이 15가 되서 문제가 해결된다.

이때 4와 3을 옮기는 조건을 생각해보면 원소의 합이 높은 쪽에서 낮은 쪽으로 원소를 옮기는 패턴을 찾을 수 있다.

(1회 : 16의 4를 14로 이동, 2회 : 18의 3을 12로 이동)

문제 또한 양쪽의 합을 일치시키는 방법을 찾는 것이므로 14와 16을 일치시키기 위해서는 16(높은 큐)에서 14(낮은 큐)로 원소의 이동이 필요하다.

 

낮은 큐에서 높은 큐로 이동이 필요한 경우가 있다 하더라도 결국에 양쪽을 일치 시키기 위해서는 높은 큐에서 낮은 큐로 이동이 필수이기 때문에 최적의 방법을 찾기 위해서는 이 조건이 유효하고 생각하고 코드를 구성했다.

 

 

 

 

반복문 탈출 조건을 찾는 것은 쉽지 않았다. 결국 내가 제출한 해법이 최적의 조건인지 확인은 하지 못했다. 

내가 생각한 방법은 단순했다. queue1과 queue2의 모든 원소를 바꾸면 queue1 길이의 2배만큼 횟수가 필요하고 다시 모든 원소를 바꿔 원래의 모습으로 만들면 queue1 길이의 2배만큼 필요해 총 len(queue1) * 4 만큼 횟수가 필요하다.

 

원래의 모습으로 돌아왔다면 동일한 패턴으로 반복될 수 있기 때문에 최대 횟수라고 판단해서 반복문을 탈출하는 조건으로 선택했다.

(정답을 제출하며 테스트해본 결과 len(queue1) * 3으로 해도 통과는 된다.)