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

문제설명

두 큐 합 같게 만들기
길이가 같은 두 개의 큐가 주어집니다. 하나의 큐를 골라 원소를 추출(pop)하고, 추출된 원소를 다른 큐에 집어넣는(insert) 작업을 통해 각 큐의 원소 합이 같도록 만들려고 합니다. 이때 필요한 작업의 최소 횟수를 구하고자 합니다. 한 번의 pop과 한 번의 insert를 합쳐서 작업을 1회 수행한 것으로 간주합니다.

큐는 먼저 집어넣은 원소가 먼저 나오는 구조입니다. 이 문제에서는 큐를 배열로 표현하며, 원소가 배열 앞쪽에 있을수록 먼저 집어넣은 원소임을 의미합니다. 즉, pop을 하면 배열의 첫 번째 원소가 추출되며, insert를 하면 배열의 끝에 원소가 추가됩니다.

풀이 & comment

그냥 단순히 sum()이 큰 쪽에서 popleft한 후 작은쪽으로 push 해주면 되는 간단한 알고리즘
여기서 시간통과가 문제인데

✌시간 줄이는 방법 2가지
	1. while 문 보다 for문이 빠르다
    	ㄴ while문의 조건절 연산이 없기 때문
        ㄴ 코드에서 if절이 줄어들 수록 속도는 빨라짐 - 컴구에서 배웠음 ^9^
        ㄴ for 범위 *2가 아니라 *3해줘야함 *3해줘도 최대 90만이라 시간초과x	
        	(1 ≤ queue1의 길이 = queue2의 길이 ≤ 300,000)
    2. queue1,2의 합을 비교할 때, sum()보다 직접 q1Sum,q2Sum 변수를 만들어 더하고 빼주기
    	ㄴ sum의 시간 복잡도 : O(n)
        ㄴ 반면 직접 연산하면 시간 복잡도 : 3 (대충 세줄이니까 ^^)

+) 이거 풀었던 것 같은데 왜 안풀엇지 잉오?

코드

from collections import deque
def solution(queue1, queue2):
    answer,q1Sum,q2Sum, len_ = 0,sum(queue1),sum(queue2), len(queue1)*3
    q1 = deque(queue1)
    q2 = deque(queue2)
    
    for i in range(len_):
        if q1Sum > q2Sum:
            tmp = q1.popleft()
            q1Sum -= tmp
            q2Sum += tmp
            q2.append(tmp)
        elif q1Sum < q2Sum:
            tmp = q2.popleft()
            q1Sum += tmp
            q2Sum -= tmp
            q1.append(tmp)
        else : return answer 
        answer+=1
    else:   return -1