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

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

문제를 풀다가 잘 모르겠어서 다른 블로그의 글을 참고하여 문제를 풀어보고 쓰는 글입니다.

문제 설명

쿠키의 수가 배열로 주어진다. [1,1,2,3] 두 명에게 같은 개수로 나눠 줄 수 있는 최대의 수를 출력하면 된다. 대신 l~m까지의 쿠키 m+1 ~ r 까지의 연속적인 쿠키를 나눠줘야한다.

문제 풀이

딱 보니 prefix sum을 이용하여 풀어야겠다는 생각이 들었다. 그래서 이리 저리 접근을 해봤는데 잘 안 됐다. 블로그들을 보니 3중 for문으로 해놔서 적용해보았더니 통과했다. 3중 for문은 시간초과가 날까봐 생각도 안 했었는데 if문을 통한 적절히 끊어줌으로써 속도가 괜찮나 보다.

코드

function solution(cookie) {
  const temp = [0];
  let sum = 0;
  for (let i = 0; i < cookie.length; i++) { // prefix sum을 구한다 각 구간합
    sum += cookie[i];
    temp.push(sum);
  }
  let max = 0;
	// a 부터 b 까지의 합은 temp[b] - temp[a-1] 이란 것을 알 면 된다.
  
  for (let m = 0; m < temp.length; m++) {
    let c = temp[m]; // m까지의 합이다.
    for (let r = m + 1; r < temp.length; r++) {
      let right = temp[r] - c; // m + 1 부터 r 까지의 합이다.
      if (max >= right || c < right) continue; // max가 더 크면 계산 해볼 필요가 없다. 마찬가지로 right가 c보다 더 크면 l을 줄여봤자 무용지물 이기 때문에 할 필요 없다.
      for (let l = 0; l < m; l++) { // m 보다 작을 떄까지만
        if (c - temp[l] < right) break; //temp[l] 을 뺀 값이 right 보다 작아지면 더 이상 같아질 수 없으니 break한다.
        if (c - temp[l] === right) { // temp[l]이랑 right가 같으면 max에 기록하고 break 한다.
          max = Math.max(max, right);
          break;
        }
      }
    }
  }

  return max;
}