백준 2910 < 빈도 정렬 > JavaScript

📍문제 링크

https://www.acmicpc.net/problem/2910

2910번: 빈도 정렬

 

📍알고리즘 분류

- 자료 구조

- 정렬

- 해시를 사용한 집합과 맵

- 트리를 사용한 집합과 맵

 

📍문제 풀이

- 수열이 주어지는데, 출현 빈도 순으로 정렬한다

- 빈도가 같을 수록, 먼저 등장했을 수록, 앞에 위치한다.

 

📍의사 코드

- 빈 객체를 만들고, 숫자를 키로, 출현 빈도를 밸류로 하여 저장한다.

- 동시에 첫 등장한 숫자는 unique한 배열에 push하여 순서를 저장한다.

- 원본 수열을 정렬하는데, indexOf 메서드를 사용하여 빈도가 같은 경우 인덱스가 빠르면 앞에 오게끔 설정한다.

 

📍코드 (JavaScript)

const [in1, in2] = require("fs")
  .readFileSync("/dev/stdin")
  .toString()
  .trim()
  .split("\n");

const [arrLen, uniqueNum] = in1.split(" ").map(Number);
const data = in2.split(" ").map(Number);
const obj = {};
const uniqueArr = [];

for (let el of data) {
    if (obj[el]) {
        obj[el]++;
    } else {
        obj[el] = 1;
        uniqueArr.push(el);
    }
}

data.sort((a, b) => {
    if (obj[a] < obj[b]) return 1;
    else if (obj[a] === obj[b]) return uniqueArr.indexOf(a) < uniqueArr.indexOf(b) ? -1 : 1;
    else return -1;
});

console.log(data.join(" "));

 

📍리뷰

- 일반 객체 대신 Map 객체를 사용하면 시간 복잡도를 줄일 수 있다