열매 수확

문제

[문제 설명] 길 위에 사과나무와 오렌지 나무가 있습니다. 사과 열매 하나당 1점, 오렌지 열매 하나당 -1점이라고 할 때, 길 위의 연속으로 이어진 나무에서 얻을 수 있는 최고 점수를 구하는 함수, solution을 완성해주세요. 예를 들어, 길 위에 있는 나무의 열매 중 사과 열매의 수는 양수로, 오렌지 열매 수는 음수로 표현된 fruits [-2, 5, -3, 6, 8, -1, -5, 3]가 있을 때 얻을 수 있는 최고 점수는 2번째부터 5번째까지 수확했을 때 점수인 16점(5 - 3 + 6 + 8) 입니다.

 

[제한 사항] - 열매 수확은 띄엄띄엄할 수 없으며, 연속된 나무의 모든 열매를 수확해야 합니다. - 사과 열매 하나는 1점, 오렌지 열매 하나는 -1점입니다. - 최소한 하나의 나무의 열매는 수확해야 합니다.

 

[입력 형식] - 길 위에 과일의 점수를 나타낸 fruits가 주어집니다. - fruits는 -1000 이상 1000 이하의 정수로 이루어진 배열입니다. - 길 위의 나무의 수는 1개 이상 10,000개 이하입니다.

 

[출력 형식] 길 위의 연속으로 이어진 나무에서 얻을 수 있는 최고 점수를 출력합니다.

접근 및 풀이

분류가 동적 프로그래밍이었는데 감이 안와서 그냥 패턴을 찾아서 풀었다. 주어진 과일 수들을 순차 탐색 하며 누적된 수와 음수인 수를 비교해가며 가장 큰 수를 리턴한다. 테스트케이스를 주지 않아서 오류 여부는 잘 모르겠다.

코드

function solution(fruits) {
  let acc = 0;
  let keep = 0;
  let max = 0;
  for (let i = 0; i < fruits.length; i++) {
    let now = fruits[i];
    if (max < acc) max = acc;
    if (now > 0) {
      if (acc + keep < 0) {
        acc = now;
      } else {
        acc += keep + now;
      }
      keep = 0;
    } else {
      keep += now;
    }
  }
  return acc > max ? acc : max;
}

출처

제로베이스 FE 온라인 코딩테스트

- 본 게시글은 개인의 학습 목적으로 게시한 것으로, 해당 과정의 모든 콘텐츠는 저작권법의 보호를 받습니다.
무단전재 및 재배포를 금지하며, 저작권법 위반 행위가 확인될 경우 강력하게 법적 대응합니다.