[Algorithm] 쿠키 구입

📋 문제

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

입출력 예

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

 

✏️ 풀이

범위를 구해 경우의 수를 계산하기에는 무조건 시간초과가 일어날 것이라고 생각했고 다른 방법을 생각해보았다. 기준이 되는 수를 잡고 좌우로 더해나가며 같은 경우가 될 때를 찾았다.

 

기본적인 아이디어는 다음과 같다. [1, 1, 2, 3, 1, 1]의 경우를 예시로 잡았다.

left와 right라는 변수가 있다. 추가로 좌우 누적합을 가지는 leftSum, rightSum이라는 변수도 선언했다.

기준이 되는 수는 0 인덱스부터 시작한다. 따라서 left = 0, right = 1이 된다. 이런식으로 초기값이 left = 1, right = 2 / left = 2, right = 3 / left = 3, right = 4 ... 로 진행해 나간다. 

만약 현재 초기값이 left = 2, right = 3 일 때, leftSum, rightSum은 각각 2, 3이다. 이때 이 둘을 비교해서 적은 부분을 확장시킨다. 현재 예시의 경우 2, 3으로 왼쪽 부분이 작기 때문에 left 인덱스를 -1 시켜준다. 인덱스를 감소 또는 증가시킬 때 배열의 범위를 벗어나는 경우 에러가 발생할 수 있기 때문에 인덱스 범위를 확인해야 한다. 

이제 현재 인덱스는 left = 1, right = 3가 되고 leftSum = 2 + 1, rightSum = 3으로 같이 같다. 따라서 아들에게 3개씩 나눠줄 수 있는 경우를 확인했다. 하지만 인덱스의 증감에 따라 더 큰 값을 찾을 수 있기 때문에 더 진행한다. 이때 좌우 한쪽의 인덱스를 증가시키는데 나는 left의 인덱스를 감소시켰다. 

현재 인덱스는 left = 0, right = 3가 되고 leftSum = 2 + 1 + 1, rightSum = 3로 오른쪽이 더 작다. 따라서 오른쪽 right의 인덱스를 +1해준다. 

현재 인덱스는 left = 0, right = 4가 되고 leftSum = 2 + 1 + 1, rightSum = 3 + 1로 새로이 더 큰 값을 찾았다. 따라서 answer를 갱신해주고 왼쪽 인덱스를 하나 감소시킨다. 하지만 그럴 경우 -1로 배열의 인덱스를 벗어나기 때문에 break를 해주고 다음의 경우를 탐색한다. 

 

위와 같은 식으로 모든 값을 찾고 찾을 때마다 answer와 비교하여 최대값을 갱신시키면 아들에게 줄 수 있는 최대 쿠키 개수를 찾을 수 있다.

⌨️ 코드

function solution(cookie) {
  var answer = 0;
  const cookieLen = cookie.length;

  for (let i = 0; i < cookieLen - 1; i++) {
    let left = i;
    let right = i + 1;
    let leftSum = cookie[left];
    let rightSum = cookie[right];

    while (true) {
      if (leftSum === rightSum) answer = Math.max(answer, leftSum);

      if (leftSum <= rightSum) {
        left--;
        if (left < 0) break;
        leftSum += cookie[left];
      } else {
        right++;
        if (right >= cookieLen) break;
        rightSum += cookie[right];
      }
    }
  }

  return answer;
}