JavaScript 알고리즘: 최댓값과 최솟값의 차이가 정확히 1인 가장 긴 부분 배열 찾기

문제 개요

숫자로 이루어진 배열 arr를 첫 번째이자 유일한 인수로 받는 JavaScript 함수를 작성해야 합니다.

이 함수는 배열 내에서 최댓값과 최솟값의 차이가 정확히 1이 되는 부분 배열 중 가장 긴 것의 길이를 찾아 반환해야 합니다.

예를 들어, 함수에 다음과 같은 입력이 주어졌다고 가정해 보겠습니다.

const arr = [2, 4, 3, 3, 6, 3, 4, 8];

이 경우 기대되는 출력은 다음과 같습니다.

const output = 5;

출력 설명

정답이 5인 이유는 조건을 만족하는 가장 긴 부분 배열이 [4, 3, 3, 3, 4]이기 때문입니다. 이 배열의 최댓값은 4, 최솟값은 3으로 그 차이가 정확히 1이며, 길이는 5입니다.

접근 방법

이 문제는 각 숫자의 등장 횟수를 저장하는 빈도 맵(frequency map)을 활용하면 효율적으로 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.

배열을 한 번 순회하면서 각 숫자가 몇 번 나타나는지 집계합니다.
맵의 각 키(숫자)에 대해 해당 숫자와 1만큼 큰 숫자의 등장 횟수를 더합니다.
두 값의 합 중 가장 큰 값을 결과로 반환합니다.

최댓값과 최솟값의 차이가 정확히 1이 되려면 해당 구간은 반드시 두 개의 서로 다른 값(n과 n+1)만으로 구성되어야 하므로, 이웃한 두 숫자의 빈도 합이 곧 가능한 부분 배열의 최대 길이가 됩니다.

코드 구현

다음은 위 접근 방식을 구현한 전체 코드입니다.

const arr = [2, 4, 3, 3, 6, 3, 4, 8];

const longestSequence = (arr = []) => {
   // 각 숫자의 등장 횟수를 담은 빈도 맵 생성
   const map = arr.reduce((acc, num) => {
      acc[num] = (acc[num] || 0) + 1;
      return acc;
   }, {});

   // 현재 숫자와 1 큰 숫자의 빈도 합 중 최댓값 계산
   return Object.keys(map).reduce((max, key) => {
      const nextKey = parseInt(key, 10) + 1;
      if (map[nextKey]) {
         return Math.max(max, map[key] + map[nextKey]);
      }
      return max;
   }, 0);
};

console.log(longestSequence(arr));

코드 설명

빈도 맵 생성: reduce()를 사용해 배열의 각 숫자가 몇 번 등장하는지 객체 형태로 집계합니다.
인접 숫자 검사: 맵의 각 키에 대해 key + 1인 숫자가 존재하는지 확인하고, 존재한다면 두 빈도의 합을 후보로 삼습니다.
최댓값 반환: 모든 후보 중 가장 큰 값을 최종 결과로 반환합니다.

실행 결과

위 코드를 실행하면 콘솔에 다음과 같은 출력이 나타납니다.

복잡도 분석

배열을 상수 번 순회하므로 시간 복잡도는 O(n)이며, 빈도 맵에 별도의 공간이 필요하므로 공간 복잡도 역시 O(n)입니다.