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

말 그대로 두 큐의 합을 같게 만들면 되는 문제다.

우선 list.pop()을 쓰면 시간 초과가 발생할 수 있으므로,

deque를 import해서 사용한다.

 

2로 나누었을 때 나머지가 생긴다면 두 큐로 나눌 수 없기 때문에 -1을 return하고,

 

두 큐의 sum을 무한 루프 내에서 비교하여 큰 큐의 원소가 작은 큐에 append 되는 형식으로 반복하고, 카운트 한다.

만약 두 큐의 원소가 같아질 때 answer를 리턴하고,

 

answer가 무한대로 커지지 않도록 queue의 길이 * 4 이상을 넘어갈 경우 찾을 수 없다고 가정하고 -1을 리턴한다.

from collections import deque

def solution(queue1, queue2):
    
    q1 = deque(queue1)
    q2 = deque(queue2)
    
    answer = 0

    if((sum(queue2)+sum(queue1)) % 2 != 0):
        answer = -1
        return
    
    limitNum = len(queue2) * 4
    
    while True:
        if(answer > limitNum):
            answer = -1
            break
        
        if(sum(q1) > sum(q2)):
            elem = q1.popleft()
            q2.append(elem)
            answer += 1
        elif(sum(q1) < sum(q2)):
            elem = q2.popleft()
            q1.append(elem)
            answer += 1
        else:
            break
        
    return answer