[프로그래머스]level2-두 큐 합 같게 만들기-Python[파이썬]

문제링크

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

문제설명

알고리즘

처음에 아래 코드 처럼 매 반복문 마다 q1의 총합(sum(q1))을 구하다보니 19번 ~ 24번 계속 시간초과 떴음..

    while q1 and q2:
        if sum(q1) > target: # q1->q2
            q1_pop = q1.popleft()
            q2.append(q1_pop)

--> 반복문을 돌때마다 q1의 총합을 계산하는 sum(q1)대신 q1에 원소를 추가하고 뺄 때마다 그 원소 크기만큼 빼주고 더해주는 q1_sum 변수를 만들어줌. 하지만 이렇게 만들어도 11번과 28번이 시간초과 뜸..

    while q1 and q2:
        if q1_sum > target: # q1->q2
            q1_pop = q1.popleft()
            q1_sum -= q1_pop
            q2.append(q1_pop)

--> cnt값이 일정 수준을 넘어가면 큐에 들어있는 원소로 target값을 만들 수 없는 것임.
--> 일정 수준을 찾아야함.
cnt값이 q1의 길이 + q2의 길이 + (q2의 길이 -2) 보다 같거나 커지면 이는 큐에 들어있는 원소로 target 값을 만들 수 없음.
total_len = len(q1) + len(q2) + len(q2) - 2

코드

from collections import deque
def solution(queue1, queue2):
    q1 = deque(queue1)
    q2 = deque(queue2)
    total_len = len(q1) + len(q2) + len(q2) - 2
    q1_sum = sum(q1)
    q2_sum = sum(q2)
    target_sum = q1_sum + q2_sum
    if target_sum % 2 == 0:
        target = target_sum // 2
    else:
        return -1
    cnt = 0
    while q1 != deque([]) and q2 != deque([]):
        if q1_sum > target: # q1->q2
            q1_pop = q1.popleft()
            q2.append(q1_pop)
            q1_sum -= q1_pop 
        elif q1_sum < target : # q2->q1
            q2_pop = q2.popleft()
            q1.append(q2_pop)
            q1_sum += q2_pop
        else: #두 큐의 합 같은 경우
            return cnt
        cnt += 1
        if cnt == total_len:
            return -1
    return -1