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

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

문제풀이

첫 번째 원소를 추출하는 pop과 끝에 원소를 추가하는 insert는 deque의 popleft와 append를 통해 쉽게 구현이 가능하다.

deque를 통해 queue1의 합이 클 경우, popleft 하여 queue2로 append, queue2의 합이 클 경
우, popleft 하여 queue1으로 append 하는 것을 queue1, queue2의 합이 같아질 때까지 하면 된다.

하지만 어떠한 수를 쓰더라도 queue의 합이 같아지지 않을 경우를 구하는 limit 횟수를 어떻게 구하는지가 쉽게 이해가 가지 않았다.
단순히 두 큐를 왕복한다는 생각으로 2n을 했지만 그건 옳지 않았다.

최악의 경우를 생각해보자

예를 들어, 나머지 모든 수를 더한 값과 같은 커다란 수가 한 큐의 뒷 부분에 자리하고 있다면 어떨까

queue1을 12까지 옮기고 나서야 이제 queue2를 옮기게 될 것이다.

queue2의 원소의 수는 기존 6개 + 옮긴 5개이다.
그런데 12가 맨 뒤에 있으니 12를 뺀 10개를 옮겨야 12만 남아 두 큐의 합이 같아진다.
그렇다면 옮긴 횟수는 처음 queue1에서 옮긴 횟수 5번 + queue2에서 12가 남을 때까지 옮기는 횟수 10을 더하면 15번이 된다.
즉, 최악의 경우 옮기는 횟수는 n-1(첫 큐에서 옮긴 횟수) + (n-1(첫 큐에서 옮겨진 원소 수) + n(기존의 원소 수)) - 1(마지막 옮겨진 원소)를 하면 3n - 3이 된다.
※ 3n - 3

답

from collections import deque
def solution(queue1, queue2):
    answer = 0 # 이동 횟수
    # deque 구현
    queue1 = deque(queue1) 
    queue2 = deque(queue2)
    leng = len(queue1) * 3 - 3 # 최대 이동 횟수 지정
    tot1 = sum(queue1)
    tot2 = sum(queue2)
    total = tot1 + tot2
    half = total // 2
    # 두 큐 합이 같지 않을 때 -1 return
    if total %2 != 0:
        return -1
    #큐1과 큐2 합이 같아지면 종료
    while tot1 != half:
        if answer == leng: #두 큐 합을 같게 만들 수 없을 때
            answer = -1
            break
        elif tot1 > half: #큐1의 합이 절반보다 클 때 앞 원소를 큐2로 이동
            target = queue1.popleft()
            queue2.append(target)
            tot1 -= target
            answer += 1
        elif tot1 < half: #큐2의 합이 절반보다 클 때 앞 원소를 큐1으로 이동
            target = queue2.popleft()
            queue1.append(target)
            tot1 += target
            answer += 1
    return answer