JavaScript로 합이 0 이상인 가장 긴 연속 구간 찾기

문제 설명

정수로 이루어진 배열을 입력으로 받는 JavaScript 함수를 작성해야 합니다. 이때 배열의 각 요소는 -1부터 1 사이의 값을 가집니다.

함수는 주어진 수열에서 합이 0 이상이 되는 가장 긴 연속 구간(부분 배열)의 길이를 반환해야 합니다.

예시 코드

다음은 위 문제를 해결하는 구현 코드입니다.

const arr = [-1, -1, 0, 1, 1, -1, -1, -1];
const longestPositiveSum = (arr = []) => {
   let sum = 0;
   let maxslice = 0;
   let length = arr.length;
   const sumindex = [];
   let marker = length * 2 + 1;
   for(let i = 0; i < length * 2; i++){
      sumindex[i] = marker;
   }
   for(let i = 0; i < arr.length; i++){
      sum += arr[i];
      if (sum >= 0)
         maxslice = i + 1;
      else if (sumindex[sum+length] != marker)
         maxslice = Math.max(maxslice, i - sumindex[sum+length]);
      else
         sumindex[sum+length] = i;
   };
   return maxslice;
};
console.log(longestPositiveSum(arr));

출력 결과

5

코드 동작 원리

이 알고리즘은 누적 합(prefix sum) 기법을 기반으로 동작하며, O(n)의 시간 복잡도로 문제를 해결합니다. 핵심 변수들은 다음과 같습니다.

• sum: 현재 인덱스까지의 누적 합을 저장합니다.
• maxslice: 지금까지 발견한 가장 긴 유효 구간의 길이를 저장합니다.
• sumindex: 각 누적 합 값이 처음 등장한 인덱스를 기록하는 배열입니다. 초기값은 marker로 설정되어 "아직 등장하지 않은 상태"를 나타냅니다.

반복문 내부에서는 세 가지 경우를 처리합니다.

1. 누적 합(sum)이 0 이상이면 배열의 처음부터 현재 인덱스까지 전체 구간이 조건을 만족하므로, maxslice를 i + 1로 갱신합니다.
2. 누적 합이 음수인데 이전에 동일한 누적 합이 등장한 적이 있다면, 그 지점 다음부터 현재 인덱스까지의 구간 합은 0이 됩니다. 따라서 두 인덱스의 차이로 maxslice를 갱신할 수 있는지 확인합니다.
3. 동일한 누적 합이 처음 등장했다면, 해당 인덱스를 sumindex에 기록해 둡니다.

예제 배열 [-1, -1, 0, 1, 1, -1, -1, -1]의 경우, 인덱스 0부터 4까지의 구간(-1, -1, 0, 1, 1)의 합이 정확히 0이므로 최종 결과로 5가 출력됩니다.