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

출처 : 프로그래머스, https://school.programmers.co.kr/learn/courses/30/lessons/118667

프로그래머스

 

 

먼저, 생각해야 할 부분

 

먼저 이 문제를 풀기 위해서는 2가지 정도를 생각해보아야한다.

하나는 큐의 합을 같게 만드는 가장 적은 횟수를 구하는 방법이고, 다른 하나는 큐의 합을 같게 만들 수 없음을 판별하는 방법이다.

 

1. 큐의 합을 같게 만드는 가장 적은 횟수를 구하는 방법

 

2개의 큐 중 합이 큰 쪽의 성분을 빼서 작은 쪽에 넣는 방법을 반복하면 된다.

합이 큰 쪽에서 작은 쪽으로 성분이 이동하며 맞춰지기 때문에 가장 적은 횟수로 투 큐의 합을 같게 만들 수 있다.

 

2. 큐의 합이 같아질 수 없음을 판별하는 방법

 

이 경우를 생각하기 위해서는 반대로 큐의 합을 같게 만들 수 있을 때 가장 최악의 경우의 수를 생각해봐야한다.

만약 이보다 더 많은 횟수를 반복한다면, 두 큐를 같게 만들 수 없음을 알 수 있기 때문이다.

 

그렇다면 가장 최악의 경우는 어떤 경우일까?

가장 쉽게 생각할 수 있는 경우는 두 queue가 다시 원래 자리로 돌아오는 경우일 것이다.

이 경우 최대 이동 횟수는 큐의 길이 * 4라고 생각해볼 수 있겠다.

그런데 이것도 좀 미심쩍어서 여러 곳을 찾아봤고,  이곳에서 예시를 들어 설명을 해주는 것을 보았다.

 

링크를 보기 전에는 나는 대충 아래와 경우를 생각해봤었는데 위의 링크에서는 구체적인 숫자 예를 들어 설명해준다.
결론적으로 queue의 길이 * 3 정도 이동하는 것이 최악의 경우라 생각해볼 수 있겠다.

 

○○○○A

●●●●B

---

○○○○A●●●●

B

---

●

B○○○○A●●●

 

 

 

---

 

풀이

 

from collections import deque

def solution(queue1, queue2):
    count = 0
    sum1 = sum(queue1)
    sum2 = sum(queue2)
    dequeue1 = deque(queue1)
    dequeue2 = deque(queue2)
    
    while sum1 != sum2 and count < len(queue1) * 3:
        if sum1 > sum2:
            move_element = dequeue1.popleft()
            dequeue2.append(move_element)
            
            sum1 -= move_element
            sum2 += move_element
            
            count += 1
        else:
            move_element = dequeue2.popleft()
            dequeue1.append(move_element)
            
            sum1 += move_element
            sum2 -= move_element
            
            count += 1
            
    if sum1 != sum2:
        return -1
            
    return count

---

고찰

 

횟수의 한계를 어떻게 설정해야하는지 모르겠다면, 최악의 경우를 생각해서 경계선으로 삼자.

 

Github

GitHub - bh2980/Algorithm-Problem: 알고리즘 풀이 흔적들