프로그래머스 - 두 큐 합 같게 만들기(Java)

서로 다른 두 개의 배열이 주어졌을 때, 두 배열의 합을 같게 만드는 문제입니다.

각 배열의 길이를 n이라고 했을 때, 두 개 배열의 길이는 때문에 2n입니다.(조건에 의해 두 개의 배열 길이는 같습니다.)

 

두 개의 배열을 하나로 합치고, 두 개의 포인터를 사용하면 이 문제를 풀 수 있습니다.

배열의 이름을 qu라고 했을 때, 첫 번째 포인터의 초기 위치는 qu[0]입니다.

두 번째 포인터 초기 위치는 qu[n]입니다. 

 

첫 번째 포인터 위치부터 두 번째 포인터 위치까지의 합이 두 배열의 합의 절반이 되게 해야합니다.

이러기 위해서는 배열의 합이 전체의 절반보다 크면 첫 번째 포인터의 위치를 앞으로 옮겨 배열의 크기를 줄이고, 배열의 합이 전체의 절반보다 작으면 두 번째 포인터의 위치를 옮겨 배열의 크기를 늘립니다.(배열의 구성 요소는 전부 양수이기 때문에 이와같은 방법이 가능합니다.)

 

[구현 코드]

import java.util.LinkedList;
import java.util.Queue;

public class Solution {

    public static int solution(int[] queue1, int[] queue2) {
        int n = queue1.length;
        int[] qu = new int[2 * n];

        long total = 0; // 꼭 long 타입으로 해 줘야 함
        long subTotal = 0;
        for (int i = 0; i < n; i++) {
            total += queue1[i];
            qu[i] = queue1[i];
        }

        subTotal = total;

        for (int i = 0; i < n; i++) {
            total += queue2[i];
            qu[i + n] = queue2[i];
        }

        int cnt = 0;
        long sub = total / 2;
        int startPointer = 0;
        int endPointer = n - 1;

        if(!(total%2==0)){
            return -1;
        }

        while (!(subTotal == sub)) {
            if (cnt > (4 * n)) return -1;

            if (subTotal < sub) {
                endPointer++;
                if (endPointer < 2 * n) {
                    subTotal += qu[endPointer];
                }
            } else if (subTotal > sub) {
                if (startPointer <= endPointer) {
                    subTotal -= qu[startPointer];
                    startPointer++;
                } else {
                    return -1;
                }
            }
            cnt++;
        }

        return cnt;
    }
}