문제 출처

찾아보니 많은 경우 실제로 큐를 만들어 문제를 풀었던데(파이썬의 경우 deque 이용) 나는 왠지 그러면 안될 것 같아 누적합이랑 슬라이딩 윈도우로 풀었다. 다르게 풀고 싶었다기보단 그렇게 풀어야만 하는 줄 알고...
근데 조건 하나 때문에 엄청 오래 걸렸다. 실력을 더 키우자ㅠㅠ

풀이

하나의 배열

큐를 사용한다는 것은 두 배열의 기본적인 순서는 섞이지 않는다는 것이다. 즉 1번 큐에서 2번 큐로 여러번 값을 보낼 경우 2번 큐의 해당 값들의 순서는 1번 큐에서의 순서를 유지한다.

예시를 계속 보면서 풀이를 해보겠다.

queue1 = [3, 2, 7, 2]
queue2 = [4, 6, 5, 1]

위의 queue1에서 3번 연산을 수행했다고 해보자.

queue1 = [2]
queue2 = [4, 6, 5, 1, 3, 2, 7]

그럼 queue2에 queue1의 데이터가 3, 2, 7의 순서를 유지한 채 움직이고 있다는 것을 볼 수 있다. 따라서 두 큐를 붙여 하나의 배열로 보는 것이 논리적으로 가능하다.

누적합

하나의 배열을 queue라는 변수로 지정하자. 그럼 해당 배열의 특정 구간의 합을 구하는 문제로 치환되므로 누적합을 이용해 문제를 풀 수 있다.

queue = [0] + queue1 + queue2
for i in range(2, len(queue)):
	queue[i] += queue[i-1]

투 포인터(슬라이딩 윈도우)

구간합을 구하는 문제이므로 투 포인터 알고리즘으로 풀 수 있다.

half = queue[-1] // 2
l = 0
r = 1
min_cnt = 1e9
while r < len(queue):
	val = queue[r] - queue[l]
    if val < half:
        r += 1
    elif val > half:
        l += 1
    else:
        ######################
        # 주요 알고리즘이 들어갈 자리
        ######################
        l += 1    
        r += 1

주요 알고리즘

앞 예시를 다시 보자.

queue1 = [3, 2, 7, 2]
queue2 = [4, 6, 5, 1]

이 큐들을 누적합으로 만들면 다음과 같이 된다.

queue = [0, 3, 5, 12, 14, 18, 24, 29, 30]

투 포인터 l, r의 위치에 따라 적용해야 하는 논리가 달라진다. 이 문제의 핵심 부분이다.

• r이 queue1의 길이보다 작은 경우
  • queue1에서 r까지의 값을 모두 옮긴 이후 queue2에서 원래 queue2의 값과 원래 queue1에서 l번째 까지의 값을 다시 옮겨야 한다.
  • 필요한 연산 수는 r + len(queue2) + l
• r이 queue1의 길이와 같은 경우(나는 이 조건을 빨리 생각해내지 못했다....ㅠㅠㅠ)
  • queue1에서 l번째 값까지 queue2로 옮기면 된다.
  • 필요한 연산 수는 l
• l이 queue1의 길이보다 작거나 같고 r이 queue1의 길이보다 큰 경우
  • queue1에서 l의 값까지 옮기고 queue2에서 r - len(queue1)번째 값까지 옮기면 된다.
  • 필요한 연산 수는 l + r - len(queue1)
• r이 queue1의 길이보다 큰 경우
  • queue2에서 r-len(queue1)번째 수까지 옮긴 이후 queue1에서 l번째 수까지 옮기면 된다.
  • 필요한 연산 수는 r - len(queue1) + l

코드로 나타내면 아래와 같다.

if l <= len(queue1):
    if r < len(queue1):
        cnt = r + len(queue2) + l
    elif r == len(queue1):
        cnt = l
    else:
        cnt = l + r - len(queue1)
else:
    cnt = r + l - len(queue1)

코드

def solution(queue1, queue2):
    summed = sum(queue1) + sum(queue2)
    if summed % 2 == 1:
        return -1
    half = summed // 2
    if max(queue1) > half or max(queue2) > half:
        return -1

    queue = [0] + queue1 + queue2
    for i in range(2, len(queue)):
        queue[i] += queue[i - 1]
    l = 0
    r = 1
    min_cnt = 1e9
    while r < len(queue):
        val = queue[r] - queue[l]
        if val < half:
            r += 1
        elif val > half:
            l += 1
        else:
            if l <= len(queue1):
                if r < len(queue1):
                    cnt = r + len(queue2) + l
                elif r == len(queue1):  # 빼먹은 조건...ㅠㅠ
                    cnt = l
                else:
                    cnt = l + r - len(queue1)
            else:
                cnt = r + l - len(queue1)
            min_cnt = min(cnt, min_cnt)
            l += 1
            r += 1

    answer = min_cnt if min_cnt != 1e9 else -1
    return answer


if __name__ == '__main__':
    print(solution([3, 2, 7, 2], [4, 6, 5, 1]))  # 2