문제 이해하기
리터럴 값들로 이루어진 배열을 유일한 인수로 받는 JavaScript 함수를 작성해야 합니다. 이 배열에는 중복된 값이 많이 포함되어 있을 가능성이 높습니다. 목표는 배열을 정렬하되, 고유한 값 즉 빈도가 가장 낮은 값들은 앞쪽에, 빈도가 가장 높은 값들은 뒤쪽에 배치하는 것입니다.
예를 들어 입력 배열이 다음과 같다고 가정해 보겠습니다.
const arr = [4, 7, 3, 5, 5, 4, 7, 9, 2, 1, 5, 7, 5, 5, 9];
그렇다면 출력 배열은 다음과 같아야 합니다.
const output = [
3, 2, 1, 9, 9, 4,
4, 7, 7, 7, 5, 5,
5, 5, 5
];결과를 살펴보면 숫자 3, 2, 1은 각각 한 번만 등장했기 때문에 가장 앞에 배치되고, 9와 4는 두 번씩, 7은 세 번, 그리고 5는 다섯 번 등장하여 가장 뒤에 배치된 것을 확인할 수 있습니다.
해결 접근 방식
이 문제는 다음 세 단계로 해결할 수 있습니다.
- 객체(map)를 활용해 각 요소의 등장 빈도를 계산합니다.
- 빈도를 기준으로 오름차순 정렬하며, 빈도가 같은 경우에는 값이 큰 숫자가 먼저 오도록 내림차순으로 정렬합니다.
- 정렬된 결과를 순회하며 각 숫자를 해당 빈도만큼 반복해 새로운 배열에 추가합니다.
예제 코드
다음은 전체 구현 코드입니다.
const arr = [4, 7, 3, 5, 5, 4, 7, 9, 2, 1, 5, 7, 5, 5, 9];
const sortByNumbers = (arr = []) => {
const map = {};
const res = [];
for (let i = 0; i < arr.length; i++) {
map[arr[i]] = map[arr[i]] || [0];
map[arr[i]][0]++;
map[arr[i]][1] = arr[i];
}
const sorted = Object.values(map).sort((a, b) => {
if (a[0] === b[0]) {
return b[1] - a[1];
}
return a[0] - b[0]
});
for (let i = 0; i < sorted.length; i++) {
const [freq, num] = sorted[i]
for (let j = 0; j < freq; j++) {
res.push(num);
}
}
return res;
};
console.log(sortByNumbers(arr));코드 상세 설명
1단계 — 빈도 계산: 첫 번째 for 루프에서 객체 map을 사용해 각 숫자의 등장 횟수를 셉니다. 각 키의 값은 [빈도, 숫자] 형태의 배열로 저장됩니다.
2단계 — 정렬: Object.values(map)으로 빈도 정보 배열들을 가져온 뒤, 빈도(a[0])를 기준으로 오름차순 정렬합니다. 빈도가 동일한 경우에는 b[1] - a[1]을 반환하여 값이 큰 숫자가 먼저 배치되도록 합니다.
3단계 — 결과 배열 생성: 정렬된 데이터를 순회하면서 구조 분해 할당으로 빈도와 숫자를 꺼내고, 각 숫자를 빈도만큼 반복해 res 배열에 추가합니다.
출력 결과
콘솔 출력은 다음과 같습니다.
[
3, 2, 1, 9, 9, 4,
4, 7, 7, 7, 5, 5,
5, 5, 5
]이 알고리즘의 시간 복잡도는 O(n log n)입니다. 빈도 계산에 O(n), 정렬에 O(k log k)(k는 고유 요소의 개수)가 소요되므로 실용적인 성능을 제공합니다.