[2022 KAKAO TECH INTERNSHIP] 두 큐 합 같게 만들기

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

프로그래머스

 

---

 

list의 pop(n)을 사용하게 되면, O(n) 시간복잡도를 가진다.

deque의 popleft를 통해 O(1) 의 시간복잡도로 원소를 pop 해준다.

 

단순히 한쪽의 queue에서 다른 쪽의 queue로 값을 더하고 빼면서 정답을 찾는 문제이다.

종료조건의 경우 하나의 큐가 pop, append를 반복하여 처음으로 돌아올 때 필요한 횟수인 (queue1 + queue2) * 2 로

제약한다.

 

from collections import deque
def solution(queue1, queue2):
    queue1 = deque(queue1)
    queue2 = deque(queue2)
    answer = 0
    sum1 = sum(queue1)
    checkInf = len(queue1)
    sum2 = sum(queue2)
    if sum1 == sum2:
        return 0
    
    while True:
        answer += 1
        if sum1 > sum2:
            temp = queue1.popleft()
            queue2.append(temp)
            sum1 -= temp
            sum2 += temp
        else:
            temp = queue2.popleft()
            queue1.append(temp)
            sum2 -= temp
            sum1 += temp
        if sum1 == sum2:
            return answer
        if checkInf * 4 <= answer:
            return -1