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

작성일: 2024-12-20

문제 링크 : https://school.programmers.co.kr/learn/courses/30/lessons/49995

접근 방식

몇 개의 바구니를 선택하는지는 상관없다. 몇개를 선택하든지, 총 합이 같기만 하면 된다.

따라서, 투 포인트를 이용해서 구간을 정해서 쿠키의 개수를 세면 되는데

여기서 중요한 점은, 쿠키의 최대 길이가 2천이기에 효율성 테스트에서 시간 초과가 발생할 수 있다는 것이다.

따라서, 효율적으로 문제를 풀어야 한다. 필요할 때마다 양쪽 바구니에 담겨진 쿠키의 개수를 세면 안 되고, 미리 계산을 해 두고 값을 가져와서 사용해야 한다.

바로, 구간 합을 이용하면 된다.

미리 만들어 둔 sum 배열을 통해, 특정 구간의 합을 구할 수 있다.

예를 들어서, [1, 1, 2, 3] 이라는 배열이 있다면 [0, 1, 2, 4, 7] 이라는 sum 배열을 만든다.

여기서 만약 2번부터 3번 바구니에 담긴 쿠키의 개수를 알고자 한다면,
먼저 3번 바구니까지의 합을 구하고 (4), 2번 바구니 이전까지의 합을 빼 주면 된다.

결과적으로는, 3번 바구니까지의 합(4) - 1번바구니까지의 합(1) = 3임을 알 수 있다.
실제로 1과 2를 합친 3이 답이다.

이를 코드에 녹여내면 된다.

결과

소스 코드

import java.util.*;
class Solution {
    public int solution(int[] cookie) {
        int answer = 0;

        // 구간 합 미리 구하기
        int[] sum = new int[cookie.length+1];
        for(int i=1; i<=cookie.length; i++){
            sum[i] = sum[i-1] + cookie[i-1];
        }

        // 1번 바구니부터 시작해서 구간을 나누기
        for(int start=1; start<=cookie.length; start++){
            for(int end=start+1; end<=cookie.length; end++){
                int left = start;
                int right = end;

                // 투포인트를 이용한 구간 합 구하기
                while(left<right){
                    int mid = (left+right) / 2;
                    int leftSum = sum[mid] - sum[start-1]; // mid까지의 합과 start-1합을 빼기
                    int rightSum = sum[end] - sum[mid]; // 끝까지의 합과 mid까지의 합을 빼기

                    // 골고루 나뉘어졌다면, answer 값 갱신하기 while문 종료
                    if(leftSum==rightSum){
                        answer = Math.max(answer, leftSum);
                        break;
                    }
                    // 왼쪽합이 더 크다면, 오른쪽 범위 늘리기
                    else if(leftSum > rightSum){
                        right = mid;
                    }
                    // 오른쪽 합이 더 크다면, 왼쪽의 범위 늘리기
                    else{
                        left = mid+1;
                    }
                }
            }
        }

        return answer;
    }

}

느낀 점

구간 합과 투포인트를 합쳐서 풀 수 있는 문제였다.

구간 합을 구할 수 있고, 투 포인트를 통해 그 구간을 지정하여 최적의 값을 구하는 알고리즘이다.