JavaScript로 최대 빈도를 가진 가장 짧은 연속 부분 배열의 길이 찾기

문제 설명

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

이 함수의 목표는 배열 전체에서 어떤 요소든 가질 수 있는 최대 빈도(출현 횟수)와 동일한 빈도를 갖는 연속(contiguous) 부분 배열 중에서 가능한 가장 짧은 길이를 찾는 것입니다.

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

입력

const arr = [55, 77, 77, 88, 55];

출력

const output = 2;

출력 설명

입력 배열에서 요소 55와 77이 각각 두 번씩 나타나므로, 이 배열의 최대 빈도는 2입니다.

배열 전체와 같은 최대 빈도를 가지는 부분 배열들 중 가장 짧은 길이는 2입니다. 따라서 함수는 2를 반환해야 합니다.

구현 예제

다음은 이 문제를 해결하는 코드입니다 −

const arr = [55, 77, 77, 88, 55];
const shortestLength = (arr) => {
    let freq = 0
    let len = Infinity
    arr.reduce((acc, num, index) => {
       if (acc[num] !== undefined) {
          acc[num].freq += 1
          acc[num].range[1] = index
       } else {
          acc[num] = {
             freq: 0,
             range: [index, index],
          }
       }
       if (acc[num].freq > freq) {
          freq = acc[num].freq
          len = acc[num].range[1] - acc[num].range[0] + 1
       } else if (acc[num].freq === freq) {
          len = Math.min(
             len,
             acc[num].range[1] - acc[num].range[0] + 1,
          )
       }
       return acc
    }, {})
    return len
};
console.log(shortestLength(arr));

코드 동작 원리

이 코드의 핵심 로직은 다음과 같습니다.

빈도와 범위 추적: reduce 메서드를 사용해 배열을 한 번만 순회하면서, 각 숫자가 등장한 횟수(freq)와 처음 등장한 인덱스부터 마지막으로 등장한 인덱스까지의 범위(range)를 누적 객체에 기록합니다.
최대 빈도 갱신: 현재 숫자의 빈도가 지금까지 확인한 최대 빈도보다 크면, 최대 빈도 값을 갱신하고 해당 숫자의 첫 등장 위치부터 마지막 등장 위치까지의 길이로 len을 설정합니다.
최소 길이 선택: 현재 숫자의 빈도가 최대 빈도와 같다면, 기존에 저장된 길이와 비교하여 더 짧은 값을 Math.min으로 선택합니다.

여기서 중요한 아이디어는, 특정 숫자가 최대 빈도를 만족하는 가장 짧은 연속 부분 배열은 곧 그 숫자가 처음 등장한 인덱스부터 마지막으로 등장한 인덱스까지의 구간이라는 점입니다. 이 구간 안에는 해당 숫자가 모두 포함되어 있고, 양 끝을 줄이면 빈도가 줄어들기 때문입니다. 덕분에 배열을 한 번만 순회하는 O(n) 시간 복잡도로 효율적으로 정답을 구할 수 있습니다.