JavaScript에서 요소의 등장 빈도에 따라 배열 정렬하기

문제 소개

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

배열 arr에는 중복된 숫자가 포함될 수 있으며, 함수는 아래 조건에 따라 배열을 정렬해야 합니다.

빈도 우선 정렬: 배열에서 등장 횟수가 적은 요소일수록 앞쪽에 배치하고, 등장 횟수가 많은 요소는 뒤쪽에 배치합니다.
동률 처리: 두 요소의 등장 횟수가 같다면, 값 자체를 오름차순으로 배치합니다.

입력 예시

const arr = [5, 4, 5, 4, 2, 1, 12];

출력 예시

const output = [1, 2, 12, 4, 4, 5, 5];

결과 설명

숫자 1, 2, 12는 각각 한 번씩만 등장하므로 값 기준 오름차순(1 → 2 → 12)으로 먼저 배치됩니다. 그 뒤에는 두 번씩 등장하는 4와 5가 각각 연속해서 배치됩니다.

구현 코드

다음은 위 문제를 해결하는 전체 코드입니다.

const arr = [5, 4, 5, 4, 2, 1, 12];

const sortByAppearance = (arr = []) => {
   // 1단계: 값을 기준으로 먼저 오름차순 정렬
   arr.sort((a, b) => a - b);

   const res = [];
   const searched = {};

   // 특정 숫자의 등장 횟수를 세고, 복사본 배열에서 제거
   const countAppearance = (list, target) => {
      searched[target] = true;
      let count = 0;
      let index = list.indexOf(target);
      while(index !== -1){
         count++;
         list.splice(index, 1);
         index = list.indexOf(target);
      };
      return count;
   };

   // 2단계: 고유한 숫자별 등장 횟수 계산
   const map = [];
   arr.forEach(el => {
      if(!searched.hasOwnProperty(el)){
         map.push([el, countAppearance(arr.slice(), el)]);
      };
   });

   // 3단계: 등장 횟수를 기준으로 오름차순 정렬
   map.sort((a, b) => a[1] - b[1]);

   // 4단계: 정렬된 결과를 바탕으로 최종 배열 생성
   map.forEach(([num, freq]) => {
      while(freq){
         res.push(num);
         freq--;
      }
   });
   return res;
};

console.log(sortByAppearance(arr));

실행 결과

[1, 2, 12, 4, 4, 5, 5]

코드 동작 방식

사전 정렬: 배열을 값 기준으로 먼저 오름차순 정렬하여, 나중에 빈도가 같은 요소들이 자연스럽게 값 오름차순으로 배치되도록 준비합니다.
빈도 계산: 아직 확인하지 않은 숫자를 만나면 해당 숫자의 등장 횟수를 세고, 그 결과를 [숫자, 빈도] 형태의 쌍으로 저장합니다.
빈도 기준 재정렬: 저장된 쌍들을 등장 횟수 기준으로 오름차순 정렬합니다.
결과 조립: 정렬된 순서대로 각 숫자를 빈도만큼 반복해 최종 배열을 완성합니다.

참고: 더 효율적인 접근 방식

위 코드는 indexOf와 splice를 반복 호출하기 때문에 배열 크기가 커지면 성능이 저하될 수 있습니다. Map 객체로 각 숫자의 개수를 한 번에 세면 훨씬 효율적으로 구현할 수 있습니다.

const sortByAppearanceEfficient = (arr = []) => {
   const countMap = new Map();
   arr.forEach(num => {
      countMap.set(num, (countMap.get(num) || 0) + 1);
   });
   return [...countMap.entries()]
      .sort((a, b) => a[1] - b[1] || a[0] - b[0])
      .flatMap(([num, freq]) => Array(freq).fill(num));
};

console.log(sortByAppearanceEfficient([5, 4, 5, 4, 2, 1, 12]));
// [1, 2, 12, 4, 4, 5, 5]

이 방식은 배열을 한 번만 순회해 빈도를 계산하므로 대용량 데이터에서도 안정적인 성능을 보여줍니다.