JavaScript로 엄격하게 증가하는 숫자만 포함하는 가장 긴 연속 하위 배열 찾기

이번 문제에서는 숫자 배열을 첫 번째이자 유일한 인수로 받는 JavaScript 함수를 작성해야 합니다.

함수는 배열 내에서 요소들이 엄격하게 증가(strictly increasing)하는 순서로만 이루어진 가장 긴 연속 하위 배열의 길이를 반환해야 합니다.

여기서 엄격하게 증가하는 수열이란, 어떤 요소든 그 앞에 있는 모든 요소보다 항상 커야 하는 경우를 의미합니다. 즉, 같은 값이 반복되어도 안 되며 매번 이전 값보다 반드시 커야 합니다.

예시

예를 들어 다음과 같은 배열이 주어졌다고 가정해 보겠습니다.

const arr = [5, 7, 8, 12, 4, 56, 6, 54, 89];

이 배열에서 엄격하게 증가하는 가장 긴 연속 구간은 [5, 7, 8, 12]이며, 그 길이는 4입니다.

접근 방법

배열을 한 번만 순회하면서 현재 요소가 바로 앞 요소보다 크면 증가 카운트를 늘리고, 그렇지 않으면 카운트를 초기화합니다. 순회 과정에서 최대값을 계속 갱신한 뒤, 마지막에 카운트에 1을 더해 실제 요소 개수를 반환합니다. 시간 복잡도는 O(n)으로 매우 효율적입니다.

코드

const arr = [5, 7, 8, 12, 4, 56, 6, 54, 89];
const findLongest = (arr) => {
   if(arr.length == 0) {
      return 0;
   };
   let max = 0;
   let count = 0;
   for(let i = 1; i < arr.length; i++) {
      if(arr[i] > arr[i-1]) {
         count++;
      } else {
         count = 0;
      }
      if(count > max) {
         max = count;
      }
   }
   return max + 1;
};
console.log(findLongest(arr));

출력 결과

콘솔에 출력되는 결과는 다음과 같습니다.

코드 동작 원리

빈 배열이 입력되면 즉시 0을 반환합니다. count 변수는 현재까지 연속으로 증가한 횟수를 저장하며, arr[i] > arr[i-1] 조건이 참이면 1씩 증가하고 거짓이면 0으로 초기화됩니다. max는 지금까지 나온 최대 증가 횟수를 기록합니다.

마지막에 max + 1을 반환하는 이유는 증가 '횟수'가 아닌 요소의 '개수'를 세어야 하기 때문입니다. 예를 들어 [5, 7, 8, 12]에서는 증가가 3번 일어나지만 실제 요소는 4개이므로, 1을 더해 올바른 길이를 구할 수 있습니다.