programmers 두 큐 합 같게 만들기

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

프로그래머스

---

일단 이문젠 단순 list로 pop을 시켰을 시 시간초과가 뜨는 문제이다.

 

시간초과로 골머리를 썩히고 있다가, 다른 블로그를 찾아보니 deque개념을 사용했어야됬음..

 

일반 pop(0) 은 시간복잡도가 O(1)이 아닌 O(n)이란 글을 읽고 from collections import deque를 사용

 

알고리즘은 크게 어려운 문제는 아니였으나, 전체 경우를 다 탔을 경우의 수를 구하는게 리스트 하나의 길이*3 이라는 점이 함정이다.

from collections import deque
def solution(queue1, queue2):
    answer = -1
    queue1 = deque(queue1)
    queue2 = deque(queue2)
    a=sum(queue1)
    b=sum(queue2)
    c=len(queue1)*3
    cnt = 0
    while (queue1 and queue2)and c!=cnt:
        if a == b:
            return cnt

        elif a > b:
            aqpop=queue1.popleft()
            queue2.append(aqpop)
            a -= aqpop
            b += aqpop

        else:
            bqpop=queue2.popleft()
            queue1.append(bqpop)
            b -= bqpop
            a += bqpop
        cnt+=1
    return answer