두 큐 합 같게 만들기

📖 2022 KAKAO TECH INTERSHIP > 두큐 합 같게 만들기

📖What I thought

1. 각 큐 합 구하기
2. 합이 큰 큐는 pop 그걸 합이 작은 큐에 push 이걸 합 같을 때까지 반복!!!

but? 합이 같을 수 없는 경우가 존재함… 그럼 반복조건을 다르게 해야할 거 같은데.. 반복조건을 어떻게 해야할까??

1. element의 요소만큼…?아님..반례 있음
2. 흠 그럼 그거보다 +1 만큼? 도 아님…
3. 걍 요소 개수 *2 했는데 흠… 통과는 했는데 정확한 반복 조건을 모르겠넹…=ㅡ=

📖풀이

📎구현

from collections import deque
 
def solution(queue1, queue2):
    q1, q2 = deque(queue1), deque(queue2)
    sum_q1, sum_q2 = sum(q1), sum(q2)
    
    cnt = 0
    while cnt <= 2*(len(q1) + len(q2)):
        if sum_q1 > sum_q2:
            e = q1.popleft()
            q2.append(e)
            
            sum_q1 -= e
            sum_q2 += e
        elif sum_q1 < sum_q2:
            e = q2.popleft()
            q1.append(e)
            
            sum_q1 += e
            sum_q2 -= e
        else:
            return cnt
        cnt += 1
            
    return -1

📖What I learned

1. 수학적 지식도 잘 활용하자

tip

queue1과 queue2의 원소는 정수이므로, 두 큐의 총합인 홀수인 경우는 무슨 짓을 해도 서로의 값이 같아질 수 없다. 즉 -1을 반환한다. ex) queue1의 합이 20 queue2의 합이 21이라면, 서로의 총합이 같아지기 위해선 총합이 20.5여야 한다. 큐는 정수로만 이루어져 있어서 총합이 소수점으로만 나타난 경우는 발생할 수 없다.

📖관련 지식

📎Queue

📎Deque