[프로그래머스] 두 큐 합 같게 만들기 - 파이썬(Python) - 우당탕탕 개발자 되기 프로젝트

 

프로그래머스

 

1. 문제 설명

2. 풀이과정

해당 문제는 두 큐의 원소를 제거하고 추가하는 작업을 반복하면서 두 큐의 합이 동일해지도록 만드는 문제이다.

큐의 구조에 따라 제일 앞 원소를 빼서 제일 뒤에 추가한다.

처음에 두 큐의 원소 개수는 동일하다. 하여 두 큐가 작업을 수행하다가 작업을 처음 큐의 원소 개수에 4배만큼 수행하게 되면 처음 큐로 돌아오게 된다.

따라서 작업 횟수는 처음 큐의 원소 개수에 4배보다 작아야 하며 이와 같거나 커질 경우에는 절대로 각 큐의 원소 합을 같게 만들 수 없는 경우인 것이다.

또한 매 작업 수행 후 두 큐의 원소 합을 sum() 함수로 계산하면 많은 시간이 소요되므로 시간을 최소화하기 위해 처음에만 합을 계산하고 이후에는 제거하고 추가하는 값을 그때마다 더하고 빼주는 방식으로 계산하였다.

 

1. popleft() 함수를 사용하기 위해 두 큐를 deque 자료구조로 바꿔 진행한다. deque 자료구조를 사용하기 위해 deque 모듈을 불러온다. from collections import deque
2. 두 큐를 deque 자료구조로 바꾼다. queue1 = deque(queue1)  queue2 = deque(queue2)
3. 작업을 진행할 때마다 두 큐의 원소 합을 sum() 함수로 구하면 많은 시간이 소요된다. 하여 두 큐의 합을 처음에만 저장해 둔다. sum1 = sum(queue1)  sum2 = sum(queue2)
4. 각 큐의 원소가 원래 큐의 모습으로 돌아오는 작업의 횟수는 전체 원소 개수의 2배이고, 이는 처음 큐 원소의 개수에 4배이다. 최대 반복 가능 횟수를 저장해 둔다. size = len(queue1) * 4
5. 작업의 최대 반복 가능 횟수만큼 반복하며 for _ in range(size)
6. 만약 두 큐의 원소 합이 같으면 종료한다. if (sum1 == sum2): break
7. 만약 첫 번째 큐의 합이 더 크면 if (sum1 > sum2)
8. 첫 번째 큐의 원소를 제거하고 이를 저장한다. num1 = queue1.popleft()
9. 제거한 원소 값만큼 합에도 빼준다. sum1 -= num1
10. 두 번째 큐에 해당 원소를 추가한다. queue2.append(num1)
11. 추가한 원소 값만큼 합에도 더해준다. sum2 += num1
12. 반면에 두 번째 큐의 합이 더 크면 else
13. 두 번째 큐의 원소를 제거하고 이를 저장한다. num2 = queue2.popleft()
14. 제거한 원소 값만큼 합에도 빼준다. sum2 -= num2
15. 첫 번째 큐에 해당 원소를 추가한다. queue1.append(num2)
16. 추가한 원소 값만큼 합에도 더해준다. sum1 += num2
17. 해당 작업이 1회 수행되었으므로 전체 작업 수행 횟수에 1을 더해준다. answer += 1
18. 반복문이 종료된 후, 만약 작업의 횟수가 최대 반복 가능 횟수와 같거나 크면 if (answer >= size)
19. 절대로 각 큐의 원소 합을 같게 만들 수 없는 경우이므로 -1을 저장한다. answer = -1

반응형

3. 소스코드

from collections import deque

def solution(queue1, queue2):
    answer = 0
    
    queue1 = deque(queue1)
    queue2 = deque(queue2)

    sum1 = sum(queue1)
    sum2 = sum(queue2)
    
    size = len(queue1) * 4
    for _ in range(size):
        if (sum1 == sum2):
            break

        if (sum1 > sum2):
            num1 = queue1.popleft()
            sum1 -= num1
            queue2.append(num1)
            sum2 += num1
        else:
            num2 = queue2.popleft()
            sum2 -= num2
            queue1.append(num2)
            sum1 += num2

        answer += 1
    
    if (answer >= size):
        answer = -1
        
    return answer