[프로그래머스 - 118667 ] 두 큐 합 같게 하기

❓ Problem

🤔 How

설명 요약

• 크기가 같은 두 큐가 주어지고 각 큐의 원소의 총합이 같도록 각큐는 poll 과 append 를한다.
• 문제에는 언급되지 않았지만 원소의 총합이 같을때 각 큐의 크기가 같을 필요는 없다. '큐의 원소의 총합' 하도록하는 최소 횟수를 반환하여야한다.

1. 큐의 크기가 되어야하는값을 설정해야한다. 각 큐의합이 같아야하므로 (큐1 과 큐2 의 원소의 총합)/2(큐의 갯수) 가 목표치(target) 이 된다.
2. 큐1과 큐2 중 하나를 기준삼아 현재 원소의 총합과 target과 비교를통해 다음행동을 한다.
   • 합이 target과 같은경우 : 이경우는 현재 까지 한 행동 횟수를 반환한다.
     • 합이 target보다 작은경우 : 이경우 반대큐에서 값을 하나 가져온다.
   • 합이 target보다 클경우 : 이경우 현재큐에서 반대큐로 값을 이동시킨다.
3. 각 총합을 구할때 sum() 함수를 쓰면 연산이 일어날때마다 o(n) 만큼 추가적으로 연산이 낭비된다. 그래서 미리 큐1,큐2 원소의 합을 구해 놓은 이후 각 연산에서 pop append 시 원소를 해당 큐1 큐2 값에 더해주는것으로 sum() 함수의 연산을 피한다.

4. 큐 연산의 최대횟수 는 얼마가 적당할까?
   • 문제에서 두큐의 합이 불가능할경우 -1 을 리턴 하는경우가 있으므로 이는 두큐의합이 같지 않을수도 있다는 점을 알려준다.
   • 최악의 경우 q1 의 원소가 q2로 q2가 다시 -> q1 으로 다옮겨지는 큐길이의 3배만큼 검사하도록 했다.

❗ Solve

from collections import deque
def solution(queue1, queue2):
    q1,q2=deque(queue1),deque(queue2)

    current_q1_result=sum(q1)
    current_q2_result=sum(q2)

    target=(current_q1_result+current_q2_result)/2
    cnt=0
    for _ in range(len(q1)*3): # 충분히 커야함

        if current_q1_result==current_q2_result:
            return cnt

        elif current_q1_result>target:
            v=q1.popleft()
            q2.append(v)

            current_q1_result-=v
            current_q2_result+=v
        else:
            v=q2.popleft()
            q1.append(v)

            current_q2_result-=v
            current_q1_result+=v

        cnt+=1 
    return -1