문제

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

풀이

아이디어

• 우선 각 큐에 대해서 sum함수를 이용해서 각각의 합을 구한다. 이 두 개를 합해서 토탈 합계를 구할 수 있고, 이를 2로 나눠서 각 큐가 가져야 할 목표 합을 알아낼 수 있다.
• 만약 큐 A가 합이 8, 큐 B가 합이 28이라면, 목표 합은 15이다. 이때, 각각 목표 합을 달성하려면 현재 합이 더 큰 큐에서 합이 더 작은 큐로 숫자를 빼서 넘겨줘야 한다.
• 나는 이 과정을 총 2N번 반복하면 될 줄 알았다.

주의

• 여기까진 쉬운 아이디어지만, 반례가 있다. 각 큐의 길이를 N이라고 할 때, 총 2N번 반복하고도 목적을 못 이뤘다면 실패라고 생각했는데, [1, 1, 1, 1, 1], [1, 1, 1, 9, 1] 같은 경우 2N번보다 더 반복하면 목적을 달성할 수 있었다.
• 그래서 최대 3N번까지 반복문을 돌려주었다.

코드

from collections import deque
def solution(queue1, queue2):
    answer = -1
    N = len(queue1)
    s1, s2 = sum(queue1), sum(queue2)
    target = (s1 + s2) // 2
    
    if (s1 + s2) % 2 == 1:
        return -1
    
    queue1 = deque(queue1)
    queue2 = deque(queue2)
    
    #총 3N번의 시도 끝에 목표 달성 실패하면 그냥 실패임
    for i in range(N*3):
        #목표가 달성됐다면 answer는 i임
        if s1 == target:
            answer = i
            break
        #target보다 합계가 큰 곳을 popleft해서 작은곳에 넣어주기
        if s1 > target:
            num = queue1.popleft()
            s1 -= num
            queue2.append(num)
            s2 += num
        else:
            num = queue2.popleft()
            s2 -= num
            queue1.append(num)
            s1 += num
    
    return answer

명심

항상 방심하지 말고 테스트케이스를 만들어보자. 시간 남는다면 말이다.