쿠키 구입

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

프로그래머스

 

전체 쿠키를 순회하며 O ( n )

index ( m ) 를 기준으로 좌우에 최대 쿠키를 구합니다.

현재 기준 ( m ) 으로 부터 index ( left, right ) 를 움직이며 최대 쿠키를 찾습니다 O ( n )
현재 쿠키가 같더라도 더 이상 움직일 index 가 없을 때까지 순회하여 전체 쿠키에서
가장 큰 쿠키를 구합니다.

총 O ( n^2 ) 에서 해결됩니다.

function solution (cookie) {
  const num_total_cookie = cookie.length;
  // default : 0
  let max_cookie = 0;

  for (let m = 0; m < num_total_cookie - 1; m++) {
    let l = m;
    let r = m + 1;
    let sum_left = cookie[l];
    let sum_right = cookie[r];

    while (true) {
      // 값이 같으면 성공 ( 최대 값 갱신 )
      if(sum_left == sum_right && sum_left > max_cookie) {
        max_cookie = sum_left;
      }
      // 오른쪽이 작으면 오른쪽으로 index 를 보내서 쿠키를 추가함
      else if(sum_left >= sum_right && r < num_total_cookie - 1) {
        sum_right += cookie[++r];
      }
      // 왼쪽이 작으면 왼쪽으로 index 를 보내서 쿠키를 추가함
      else if(sum_left <= sum_right && l > 0) {
        sum_left += cookie[--l];
      } else {
      // 더 이상 움직일 index 가 없으면 종료
        break;
      }
    }
  }

  return max_cookie;
}