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

출처 : https://school.programmers.co.kr/learn/courses/30/lessons/118667

프로그래머스

 

풀이 방법

처음에는 두 큐의 합이 같게 만드는 알고리즘이 있을까 생각해 봤는데 떠오르지 않았다.

그래서 그냥 완전 탐색으로 합이 작은 쪽에서 큰 쪽으로 원소를 이동해 가며 특정 횟수가 넘으면 return -1 하게 풀어야겠다고 생각했다.

처음에는 sum 메서드를 활용해서 매번 loop마다 합을 구해서 비교했는데 이러면 sum 메서드 때문에 시간 초과 된다.

그래서 변수 total1, total2를 활용해서 두 배열의 합을 구해서 비교를 했다.

또 그냥 배열을 사용해서 pop(0) 메서드를 이용했는데 이러면 맨 앞 원소를 제거 후 원소를 한 칸씩 왼쪽으로 옮겨야 하므로 시간 복잡도가 O(n)이 된다. 그러므로 리스트를 deque로 변환 후 popleft()를 수행하면 O(1)으로 줄일 수 있다.

그리고 최대 횟수는 모든 원소가 바뀌었다가 다시 원상 복구할 때 수행해야 하는 수가 (전체 배열의 수 * 2)가 되므로

(전체 배열의 수 * 2)를 최대 횟수로 설정했다. 

from collections import deque

def solution(queue1, queue2):    
    queue1 = deque(queue1)
    queue2 = deque(queue2)
    answer = -2
    cnt = 0
    num_num = len(queue1) + len(queue2) ## 총 배열의 길이
    num_num = num_num * 2
    total1 = sum(queue1)
    total2 = sum(queue2)
    if (total1 + total2) % 2 != 0:
        return -1
    while True:
        if cnt > num_num:
            return -1        
        if total1 > total2:
            temp = queue1.popleft()
            queue2.append(temp)            
            total1 -= temp
            total2 += temp
        elif total1 < total2:
            temp = queue2.popleft()
            queue1.append(temp)
            total1 += temp
            total2 -= temp
        else:
            break;
        cnt += 1
    return cnt