백준 10989번 수 정렬하기-JS(JS로 풀 수 없음)

무슨 방법을 써도 메모리 초과남. 백준에서 js로 풀 수 없음.
어찌됐든 계수정렬 알고리즘 공부할 수 있어서 좋았음.

계수정렬(Counting sort)

시간복잡도가 무려 N인 엄청 빠른 알고리즘.
하나의 배열을 만들고, 정렬하고 싶은 배열의 숫자에 해당하는 자리에 수를 더해주는 것. 자리를 바꾸는 것이 아니라 숫자확인 후 +1 이런식이여서 짱빠름.

1. 빈도수를 세어줄 새로운 배열(arrange) 생성
2. 정렬하고 싶은 배열의 값(arr[i])-1의 index를 가지는 arrange배열의 요소에 +1을 해준다.
3. 각 숫자들의 빈도수를 나타낸 배열로 완성
4. 해당 요소의 값만큼 요소를 반복해서 출력하면 arr배열을 정렬한 것과 같아진다.

더 정리 필요

- 제출한 코드

const fs = require('fs');
const filePath = process.platform === 'linux' ? '/dev/stdin' : './input.txt';
let input = fs.readFileSync(filePath).toString().trim().split('\n');
//3:48
//알게된 것 Math.max.apply(null, arr);
let N = Number(input.shift());
let arr = input.map(x => +x);
let max = Math.max.apply(null, arr);
let arrange = new Array(max);
arrange.fill(0);
let answer = '';
for(let i = 0; i < N; i++) {
    arrange[arr[i]-1]++;
}

for(let i = 0; i < arrange.length; i++) {
    if(arrange[i] !== 0) {
        for(let j=0; j < arrange[i]; j++) {
            answer += (i+1) + '\n';
        }
    }
}
console.log(answer);