두 큐 합 같게 만들기 - Python으로 풀이

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

프로그래머스

문제해석

길이가 같은 큐를 두개 준다. 그리고 나서 FIFO 구조로 POP을 하면 맨앞에것이 빠지고 insert를 하면 맨 마지막 인덱스 뒤에 추가가 된다.

그렇게 반복하여 두 큐를 같게 해라!가 문제였다.

그냥 단순하게 생각을 해보았다. 두 큐가 주어지면 각 합을 구한다음에 더 큰 놈에서 앞에꺼를 POP해서 작은놈한테 insert를 해주면서 맞추어 나가는 단계를 진행하면 되지 않을까? 

여기서 두 큐의 합이 끝까지 같아지지 않다면 -1을 출력하라고 했는데 처음에 주어진 두 큐의 합이 만약 홀수이다면 -1을 출력해주면 된다고 생각을 하였다. 왜? 두 개를 더했는데 홀수가 나올수는 없기때문에!

def solution(queue1, queue2):
    answer = 0
    maxnum = len(queue1)
    sum1 = sum(queue1)
    sum2 = sum(queue2)
    if((sum1 + sum2) %2 == 1):
        return -1 
    while True : 
        if(sum1>sum2):
            queue2.append(queue1[0])
            del queue1[0]
        elif(sum1<sum2):
            queue1.append(queue2[0])
            del queue2[0]
        sum1 = sum(queue1)
        sum2 = sum(queue2)
        answer += 1
        if(sum1==sum2):
            break
        if answer == maxnum * 3 : 
            return -1
    return answer

1트 실패. 너무나 바보같은 실수를 하였다. sum함수는 그자체로 시간복잡도가 O(N)이기에 while문은 시간복잡도가 O(N^2)이 되게 된다. 그래서 굳이 저기안에서 큐를 다시 돌며 sum을 구해주는 것이 아닌 그냥 바로 sum에서 마지막것을 빼고 새로 넣는 것을 더해주면 sum을 호출하지 않아도 되어 시간복잡도가 O(N)으로 된다. 그리고 del도 마찬가지로 시간복잡도가 O(N)이기에 그냥 deque를 써서 해주면 끝이였다. answer이 최대 처음준 큐의 3배에서 멈춘 이유는 3번을 총 왔다갔다하면 다시 본래의 큐가나오기에 그 이상은 할 필요가 없다.

from collections import deque
def solution(queue1, queue2):
    answer = 0
    maxnum = len(queue1)
    deque1 = deque(queue1)
    deque2 = deque(queue2)
    sum1 = sum(queue1)
    sum2 = sum(queue2)
    if((sum1 + sum2) %2 == 1):
        return -1 
    while True : 
        if(sum1>sum2):
            a = deque1.popleft()
            deque2.append(a)
            sum1-=a
            sum2+=a
        elif(sum1<sum2):
            b= deque2.popleft()
            deque1.append(b)
            sum1+=b
            sum2-=b
        else:   
            return answer
        answer += 1
        if answer == maxnum * 3 : 
            return -1
    return answer

2트 deque로 시간복잡도 문제 해결