프로그래머스 [Lv. 4] 쿠키 구입 {언어 : JavaScript}

문제 링크

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

프로그래머스

정답 코드

function solution(cookie) {
    let answer = 0;
    const n = cookie.length;
    const dp = Array(n).fill(0);
    dp[0] = cookie[0];
    for (let i = 1; i < n; i++) {
        dp[i] = cookie[i] + dp[i-1];
    }
    // mid를 기준으로 좁혀오자
    for (let mid = 0; mid < n; mid++) {
        let left = 0;
        let right = n - 1;
        while (left <= right) {
            const lv = left === 0 ? dp[mid] : dp[mid] - dp[left-1];
            const rv = dp[right] - dp[mid];
            if (lv > rv) {
                left += 1;
            } else if (lv < rv) {
                right -= 1;
            } else {
                answer = Math.max(answer, lv);
                break;
            }
        }
    }
    
    return answer;
}

풀이 방법

1. 누적 배열을 만든다.
   1. 배열을 만드는 이유
      1. [1, 2, 3, 4, 5] 배열이 있다고 할 때
      2. [1, 3, 6, 10, 15]가 누적 배열이 된다.
      3. 1번 인덱스에서 4번 인덱스까지의 합을 구하고 싶으면
      4. dp[4] - dp[0] = 15 - 1 = 14
      5. 위와 같이 계산하면 된다.
2. mid를 0부터 n까지 탐색한다.
   1. 탐색하면서 mid를 기준으로 좌우값을 구한다.
   2. 좌값이 큰 경우 좌측에서 범위를 줄이고
   3. 우값이 큰 경우 우측에서 범위를 줄인다.
   4. 값이 같다면 while을 벗어난다.
      • 왜냐하면 범위가 줄어들면 어차피 값은 작아지고 우리가 찾고 싶은 값은 최대값이기 때문이다.
3. while을 벗어나고 나온 값을 answer와 비교해서 큰 값으로 치환한다.
4. 반복문 종료 후 answer를 리턴하면 끝!

느낀점

• 이렇게 푸는게 맞나 싶었지만 맞아서 다행이다.
• 풀이 방법을 다시 떠올리면 좋을 것 같아서 다시 풀어 보면 좋을 것 같다.