[프로그래머스] 쿠키 구입

문제 설명

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

문제 풀이

• 누적합과 이분 탐색을 이용하여 풀이하였다.
• 우선 이중 for문으로 L과 R값을 정해준다.
• L,R이 정해지면 L~M, M+1~R을 나눌 M을 정해야하는데 이때 이분탐색을 사용해준다.
• 이분 탐색시에 (L~mid), (mid+1~R)을 구하여 비교하기 위해 구간합을 구해야 하는데 이를 O(1)로 수행하기 위해 배열에 대해 누적합을 구하고 이를 이용한다.
• 추가로 L, R을 정할때 sum(L~R) / 2 보다 현재 최대값이 크거나 같다면 이분탐색을 진행하지 않는 최적화가 필요하다.

소스 코드 (JAVA)

class Solution {
    public int solution(int[] cookie) {
        int N = cookie.length;
        int[] preSum = new int[N];
        //구간합 O(1)을 위해 누적합 배열 구하기
        int sum = 0;
        for (int i = 0; i < N; i++) {
            sum += cookie[i];
            preSum[i] = sum;
        }

        int result = 0;
        for (int i = 0; i < N-1; i++) {
            for (int j = i+1; j < N; j++) {
                sum = preSum[j] - (i-1 < 0 ? 0 : preSum[i-1]);
                if (sum / 2 <= result) continue;
                //i ~ M, M+1 ~ j 범위일 때, M 구하기
                int lo = i;
                int hi = j;
                int before = -1;
                while(lo < hi) {
                    int mid = (lo + hi) / 2;
                    if (mid == before) break;
                    before = mid;
                    //i ~ mid 구간합
                    int sum1 = preSum[mid] - (i-1 < 0 ? 0 : preSum[i-1]);
                    int sum2 = preSum[j] - preSum[mid];
                    if (sum1 > sum2) hi = mid;
                    else if (sum1 < sum2) lo = mid;
                    else {
                        result = Math.max(result, sum1);
                        break;
                    }
                }
            }
        }
        return result;
    }
}