자바스크립트에서 숫자 배열을 빈도 기준으로 정렬하는 방법

반복되는 숫자가 포함될 수 있는 숫자 배열을 입력받아 정렬하는 자바스크립트 함수를 작성해야 합니다.

이 함수는 배열을 다음과 같은 규칙에 따라 정렬해야 합니다. 등장 횟수(빈도)가 가장 적은 요소부터 먼저 배치하고, 그 뒤로 빈도가 점점 높아지는 순서대로 나머지 요소들을 배치합니다.

문제 예시

예를 들어, 입력 배열이 다음과 같다고 가정해 보겠습니다.

const arr = [1, 1, 2, 2, 2, 3];

각 숫자의 등장 빈도를 살펴보면 다음과 같습니다.

• 3 → 1번 등장
• 1 → 2번 등장
• 2 → 3번 등장

따라서 정렬된 결과 배열은 다음과 같아야 합니다.

const output = [3, 1, 1, 2, 2, 2];

구현 코드

const arr = [1, 1, 2, 2, 2, 3];
const frequencySort = (arr = []) => {
    let map = {};
    for (let i = 0; i < arr.length; i++) {
        map[arr[i]] = (map[arr[i]] || 0) + 1;
    };
    return arr.sort((a,b) => map[a] - map[b] || b - a);
};
frequencySort(arr);
console.log(arr);

코드 동작 원리

위 코드의 핵심 로직을 단계별로 살펴보겠습니다.

1. 빈도 계산: 객체(map)를 사용해 배열의 각 숫자가 몇 번 등장했는지 카운트합니다. (map[arr[i]] || 0) + 1 표현식은 해당 숫자가 처음 등장하면 1로 초기화하고, 이미 존재하면 기존 값에 1을 더합니다.
2. 빈도 기준 정렬: sort() 메서드의 비교 함수에서 map[a] - map[b]를 반환하여, 빈도가 낮은 숫자가 앞에 오도록 오름차순 정렬합니다.
3. 동일 빈도 처리: 두 숫자의 빈도가 같으면 map[a] - map[b]가 0이 되므로, 이때 b - a가 평가되어 값이 큰 숫자가 앞에 위치하게 됩니다.

출력 결과

위 코드를 실행하면 다음과 같은 결과가 출력됩니다.

[ 3, 1, 1, 2, 2, 2 ]

마무리

이 방법은 객체(해시 맵)를 활용해 O(n) 시간에 각 숫자의 빈도를 계산한 뒤, sort() 메서드로 최종 정렬하므로 전체 시간 복잡도는 O(n log n)입니다. 빈도 기반 정렬은 코딩 테스트에서 자주 출제되는 유형이므로, 비교 함수에서 조건을 연결하는(|| 연산자 활용) 이 패턴을 잘 익혀두면 다양한 문제에 응용할 수 있습니다.