[JavaSrcipt] Baekjoon - 10989 : 수 정렬하기 3

✅ 수의 범위가 작다면 카운팅 정렬을 사용하여 더욱 빠르게 정렬할 수 있습니다.

 

문제

N개의 수가 주어졌을 때, 이를 오름차순으로 정렬하는 프로그램을 작성하시오.

입력

첫째 줄에 수의 개수 N(1 ≤ N ≤ 10,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 10,000보다 작거나 같은 자연수이다.

출력

첫째 줄부터 N개의 줄에 오름차순으로 정렬한 결과를 한 줄에 하나씩 출력한다.

 

예제입력	예제출력
10 5 2 3 1 4 2 3 5 1 7	1 1 2 2 3 3 4 5 5 7

 

⭕ 풀이

 

const input=require('fs').readFileSync('/dev/stdin').toString().trim();
const t=input.shift();
// 10
let arr=input.split(' ').map(x=>Number(x));
// 5 2 3 1 4 2 3 5 1 7

let max=Math.max(...arr);

let countArr = new Array(max+1);
countArr.fill(0);
// 0 0 0 0 0 0 0 0

for(let i=0;i<arr.length;i++){
    countArr[arr[i]]++;
}
//arr[0]=5  countArr[5]++ 0 0 0 0 0 1 0 0

for(let i=0;i<countArr.length;i++){
    if(countArr[i]){
        for(let j=0;j<countArr[i];j++){
            console.log(i);
        }
    }
}

카운팅정렬 (계수정렬) 은 문제에서 범위조건이 있는경우에 한해서 굉장히 빠르다.

하지만 범위조건이 작을때에 유리하다.

예를들어 정렬해야하는수가 작은데 수의 끝값이 크다면?

3, 65, 68, 34, 134567 를 정렬해야한다면

정렬해야할 갯수는 5개지만 134567까지 배열을 만들어야해서 좋지못하다.

 

우선 코드를 해석해보자면

정렬해야할 값들중 가장 큰값+1을하여 그만큼의 배열을 만든후 0으로 채운다.

 

첫번째 for문에서

countArr[arr[i]]를 ++ 한다.

i=0일때 arr[i]는 5이므로 countArr의 [5]인덱스를 ++하게된다.

이때 0 0 0 0 0 1 0 0 이된다.

이 과정을 다 반복하면

countArr = [0, 2, 2, 2, 1, 2, 0, 1] 이 되며

0인덱스부터 0 1 2 3 4 5 6 7각각의 갯수를 의미한다.

 

두번째 for문의 if문에서  countArr 길이까지

countArr의 [i] 인덱스가 참이라면 즉 0이아니라면

이너루프의 j가 countArr[i]의 값까지 반복해서 i를 출력한다.

 

즉 i=3으로 예를들면 

countArr[3] 은 2로 참이다.

j=0부터 j<2까지 즉 j++를하며 0일때한바퀴 1일때 한바퀴

총 두번을 console.log(3) 을 하는것이다.

 

 

즉 작은범위가 주어졌다면 각 인자(?)들의 갯수를 카운팅한 뒤

해당 카운팅값만큼 해당 인자를 반복출력하는 정렬이다.

 

하지만 해당문제가 메모리초과등의 문제가 많았나보다.

문제자체의 정답률이 낮고 Node.js에서는 맞은사람이 없는걸보니

카운팅정렬은 이런식으로 구현하는구나 하고 넘어가야겠다.

 

 

 

-출처

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