문제

과자를 바구니 단위로 파는 가게가 있습니다. 이 가게는 1번부터 N번까지 차례로 번호가 붙은 바구니 N개가 일렬로 나열해 놨습니다.

철수는 두 아들에게 줄 과자를 사려합니다. 첫째 아들에게는 l번 바구니부터 m번 바구니까지, 둘째 아들에게는 m+1번 바구니부터 r번 바구니까지를 주려합니다. 단, 두 아들이 받을 과자 수는 같아야 합니다(1 <= l <= m, m+1 <= r <= N). 즉, A[i] 를 i번 바구니에 들어있는 과자 수라고 했을 때, A[l]+..+A[m] = A[m+1]+..+A[r] 를 만족해야 합니다.

각 바구니 안에 들은 과자 수가 차례로 들은 배열 cookie가 주어질 때, 조건에 맞게 과자를 살 경우 한 명의 아들에게 줄 수 있는 가장 많은 과자 수를 return 하는 solution 함수를 완성해주세요. (단, 조건에 맞게 과자를 구매할 수 없다면 0을 return 합니다)

제한사항

• cookie의 길이는 1 이상 2,000 이하입니다.
• cookie의 각각의 원소는 1 이상 500 이하인 자연수입니다.

풀이

조건

• 1 <= l <= m, m+1 <= r <= N 일때, A[l] +...+ A[m] == A[m+1] +...+ A[r]

위 조건을 만족하는 값 중 최대값을 반환해야 한다. 즉, cookie의 범위 안에 있는 모든 range(l ... r) 에 위 조건을 만족하는 m을 찾고 최대값을 찾으면 된다. 이때 확인해야하는 range의 길이는 2 <= range의 길이 <= cookie.length가 된다. 나는 범위안에 있는 모든 length를, 그리고 해당 length를 만족하는 모든 l 과 r의 값에 대해 조건을 만족하는 m이 있는지 확인했다. m의 값을 찾기위해서는 binary search를 사용했다.

• arr에 그 전 인덱스까지의 쿠키 개수를 모두 더한 값을 저장한다 (arr[x] - arr[y] == cookie[y] + ... + cookie[x - 1])
• 처음에 쿠키의 길이와 똑같이 range의 길이, length를 정해준 뒤, 해당 length에 있는 range를 모두 확인 했다면 length가 2보다 작거나 같아질때까지 length를 줄여준다
• length에 해당하는 모든 range에 조건을 만족하는 mid 값이 있는지 확인한다. 이떄, mid 값을 찾기위해 Binary Search를 이용한다
• 모든 range를 확인 후, 최대값을 반환한다 (없다면 0)

코드

class Solution {
    int[] arr;
    public int solution(int[] cookie) {
        int answer = 0;
        
        // 쿠키의 합계값 저장 (index = 1 부터 시작)
        arr = new int[cookie.length + 1];
        for (int i = 1; i < arr.length; i++) {
            arr[i] = cookie[i - 1] + arr[i - 1];  
        }
        
        int begin = 1;
        int end = arr.length - 1;
        int left = 1;
        int right = arr.length - 1;  
        int cnt = 0;
        int length = end - begin + 1; //r - l + 1
        int maxCnt = cookie.length - length;
        
        // length = range(2 ... cookie.length) 일때  쿠키의 합계 값이 같아지는 mid 가 있다면 answer를 업데이트 해준다
        while (length > 1 && left <= right) {
            int mid = (right + left) / 2;
            int sum1 = sumOfRange(begin, mid); // cookie[begin] + ... + cookie[mid]
            int sum2 = sumOfRange(mid + 1, end); // cookie[mid + 1] + ... + cookie[end]
            if (sum1 == sum2) { 
                // answer의 값을 업데이트 해준다
                if (answer < sum1) answer = sum1;
                //이 range에서 합계가 같은 mid를 찾았으니 다음 range로 넘어간다
                left = right + 1;        
            }
            else if (sum1 > sum2) {
                right = mid - 1;
            }
            else {
                left = mid + 1;
            }
            if (left > right) {
                cnt++;
                if (cnt <= maxCnt) {
                    begin++;
                    end++;
                    left = begin;
                    right = end;
                }
                else {
                    cnt = 0;
                    length--;
                    begin = 1;
                    end = begin + length - 1;
                    left = begin;
                    right = end;
                    maxCnt = cookie.length - length;
                }
            }
        }
        return answer;
    }
    
    // start 인덱스부터 end 인덱스까지의 쿠키 갯수 리턴 (start & end 포함)
    public int sumOfRange(int start, int end) {
        return arr[end] - arr[start - 1];
    }
}