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

😀문제 설명

과자를 바구니 단위로 파는 가게가 있습니다. 이 가게는 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 이하인 자연수입니다.

---

😂입출력 예

cookie	result
[1,1,2,3]	3
[1,2,4,5]	0

---

🤣입출력 예 설명

입출력 예 #1

첫째 아들에게 2, 3번 바구니를, 둘째 아들에게 4번 바구니를 사주면 두 아들은 각각 과자 3개를 받습니다.

입출력 예 #2

주어진 조건에 맞게 과자를 살 방법이 없습니다.

---

😄나의 풀이

해당 문제는 포인터 문제이다. 효율성 테스트를 거치기 때문에, 미리 부분합을 더해놓고 이후에 사용하는 방법이 유리하다.
해당 풀이는 포인터를 특정 인덱스에 위치하게 하고, 확장 가능한 범위 내에서 순회하며 비교한다.

function solution(cookie) {
    let answer = 0; // 결과 값을 저장할 변수 초기화

    const prefixSum = Array(cookie.length+1).fill(0); // 부분 합 배열 초기화
    for(let i=1; i<=cookie.length; i++) { // 부분 합 계산
        prefixSum[i] = prefixSum[i-1] + cookie[i-1];
    }
    
    for(let m=0; m<cookie.length-1; m++) { 
        let l=m, r=m+1;
        while(l>=0 && r<cookie.length) {
            const sumL = prefixSum[m+1] - prefixSum[l]; // 첫째 아들이 받는 과자 수 계산
            const sumR = prefixSum[r+1] - prefixSum[m+1]; // 둘째 아들이 받는 과자 수 계산

            if(sumL === sumR) { 
                answer = Math.max(answer, sumL); // 같은 경우, 최대 값 업데이트
                r++;
            } else if(sumL < sumR) { 
                l--;  // 첫째 아들이 받는 과자가 적은 경우, 왼쪽 포인터 이동
            } else {
                r++;  // 둘째 아들이 받는 과자가 적은 경우, 오른쪽 포인터 이동
            }
        }
    }

    return answer;
}