프로그래머스_쿠키 구입 <Java>

이 문제에서 사용된 알고리즘은 투 포인터(Two Pointers) 알고리즘입니다. 투 포인터 알고리즘은 배열 내에서 두 개의 포인터(인덱스)를 사용해 문제를 해결하는 방법으로, 주로 배열을 양쪽에서 비교하거나 합을 조정할 때 사용됩니다.

투 포인터 알고리즘 개요

• 투 포인터 알고리즘은 두 개의 포인터를 사용해 배열을 순차적으로 탐색하면서 조건에 맞는 값을 찾는 방법입니다.
• 배열의 특정 구간을 탐색하거나 두 부분 간의 합이나 차이를 비교하는 문제에서 자주 쓰입니다.
• 일반적으로 두 개의 포인터가 배열의 서로 다른 위치에 놓이고, 필요한 상황에 따라 한 포인터를 왼쪽 또는 오른쪽으로 이동시킵니다.

이 문제에서의 투 포인터 알고리즘은 배열을 중간 기준으로 나눠, 왼쪽과 오른쪽에서 각각의 부분 합을 비교하면서 최적의 값을 찾는 방식입니다.

 

class Solution {
    public int solution(int[] cookie) {
        int answer = 0;
        int num = cookie.length;
        
        // i는 중간 지점
        for (int i = 0; i < num - 1; i++) {
            int leftSum = cookie[i];
            int rightSum = cookie[i + 1];
            
            int left = i;
            int right = i + 1;
            
            // 투 포인터로 합을 비교
            while (left >= 0 && right < num) {
                if (leftSum == rightSum) {
                    answer = Math.max(answer, leftSum); // 더 큰 값을 갱신
                }
                
                if (leftSum <= rightSum && left > 0) {
                    left--;
                    leftSum += cookie[left];
                } else if (rightSum < leftSum && right < num - 1) {
                    right++;
                    rightSum += cookie[right];
                } else {
                    break;
                }
            }
        }
        
        return answer;
    }
}