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

문제 접근

두 큐의 크기가 같다는 것과 큐의 특징을 이해하면 사실 이 문제는 투포인터의 부분합이 매칭되는 경우를 찾는 것과 동일한 문제가 된다.

우선, 두 큐가 서로 꼬리에 꼬리를 물며 뫼비우스의 띠와 같은 모양을 이룬다고 머릿속에 그려보면 편할 것 같다. 그리고 이 뫼비우스의 띠 위에 올라간 숫자들이 순차적으로 쭉 흐르면서 마치 원형큐와 같은 형태로 움직이다가 어느순간 연속된 부분합이 총합의 절반과 일치하는 부분구간을 찾을 수 있을 것이다. 그런 구간들을 모두 찾아서, 그 형태를 만들기 위한 큐의 이동횟수들 중 최소를 구하면 된다.

아래 사진을 보면 좀 도움이 될 것 같다.

문제 풀이

s와 e를 활용한 투 포인터로 연속 부분합이 M인 구간을 찾았다.
이때, s는 포함이고 e는 포함하지 않고 그것보다 하나 앞서 있다는 것에 주목하면 될 것 같다.

import java.io.*;

class Solution {
    public int solution(int[] queue1, int[] queue2) {        
        long total = 0;
        int N = queue1.length;
        int[] q = new int[2*N];

        for(int i=0; i<N; i++) { 
            q[i] = queue1[i]; 
            total+=queue1[i];
        }
        for(int i=0; i<N; i++) { 
            q[N+i] = queue2[i];
            total+=queue2[i];
        }
        if(total % 2 != 0) return -1;
        
        int answer = 10_0000_0000;
        int QN = 2*N;
        int start = 0, end = 0;
        long sum = 0;
        long M = total / 2;
        while(start <= end) {
            if(sum >= M) sum -= q[start++];
            else if(end == QN) break;
            else sum += q[end++];
                
            if(sum == M) { 
                int curCount = 10_0000_0000;
                if (end == N) {
                    curCount = start; 
                } else if (end == QN) {
                    if (start >= N) {
                        curCount = start - N;
                    } else {
                        curCount = N + start;
                    }
                } else if (end < N) {
                    curCount = end + N + start; 
                } else {
                    if (start>=N) {
                        curCount = (end-N) + N + (start-N);
                    } else {
                        curCount = start + (end-N);
                    }
                }
                answer = Math.min(answer, curCount);
            }
        }
        
        if (answer != 10_0000_0000) return answer;
        return -1;
    }
}

큐의 특성을 활용한 매우 좋은 문제였다고 생각한다. 개인적으로, 부분합 투포인터를 오랜만에 짰더니 좀 헤맸다...