JavaScript에서 배열의 차수(Degree)와 최단 연속 부분 배열 길이 구하기

배열의 차수(degree)란 배열을 이루는 요소 중 가장 많이 등장하는 요소의 빈도수, 즉 최대 출현 횟수로 정의됩니다.

예를 들어 다음 배열을 살펴보겠습니다.

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

이 배열에서 숫자 3은 총 4번 등장하므로, 해당 배열의 차수는 4가 됩니다.

문제 정의

리터럴 값으로 구성된 배열을 입력받는 JavaScript 함수를 작성해야 합니다. 이 함수의 목표는 전체 배열과 동일한 차수를 가지면서 길이가 가장 짧은 연속 부분 배열(subarray)의 길이를 반환하는 것입니다.

접근 방법

이 문제는 Map 객체를 활용하면 효율적으로 해결할 수 있습니다.

• 각 요소에 대해 첫 등장 인덱스, 마지막 등장 인덱스, 빈도수 세 가지 정보를 저장합니다.
• 첫 번째 순회에서 모든 요소의 정보를 기록하면서 최대 차수(maxDegree)를 계산합니다.
• 두 번째 순회에서 차수가 maxDegree와 일치하는 요소들을 대상으로, 첫 등장 인덱스와 마지막 등장 인덱스의 구간 길이를 비교하여 최솟값을 구합니다.

구현 코드

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

const findShortestSubArray = (arr = []) => {
   let range = new Map(), maxDegree = 0, minLength = Infinity;

   // 1단계: 각 요소의 시작/끝 인덱스와 빈도수 기록
   for(let i = 0; i < arr.length; i++){
      if(range.has(arr[i])) {
         let start = range.get(arr[i])[0];
         let degree = range.get(arr[i])[2];
         degree++;
         range.set(arr[i], [start, i, degree]);
         if(degree > maxDegree)
            maxDegree = degree;
      }
      else {
         let degree = 1;
         range.set(arr[i], [i, i, degree]);
         if(degree > maxDegree)
            maxDegree = degree;
      }
   }

   // 2단계: 최대 차수를 가진 요소 중 가장 짧은 구간 찾기
   for (let key of range.keys()){
      let val = range.get(key);
      if(val[2] === maxDegree){
         let diff = (val[1] - val[0]) + 1;
         if(diff < minLength) minLength = diff;
      }
   }
   return minLength;
};

console.log(findShortestSubArray(arr));

실행 결과

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

8

결과 분석

결과가 8인 이유는 다음과 같습니다. 숫자 3은 인덱스 2, 3, 7, 9에 위치하며 총 4번 등장합니다. 따라서 전체 배열과 같은 차수(4)를 유지하려면 인덱스 2부터 인덱스 9까지의 구간이 반드시 포함되어야 하고, 이 구간의 길이는 9 − 2 + 1 = 8이 됩니다.

이 알고리즘은 배열을 두 번 순회하므로 시간 복잡도는 O(n), 추가로 사용하는 Map의 공간 복잡도 역시 O(n)으로 효율적입니다.