baekjoon. 수 정렬하기 3

풀이

이번에도 정렬이지만 시간 복잡도가 O(n)이 되게 구현해야한다

카운팅 정렬을 사용하면 되는데

내가 설명하기 보다는 굉장히 참고하기 좋게 포스팅해둔 블로그가 있어서 남긴다

Counting Sort : 계수 정렬

구현

첫번째

const input = require('fs').readFileSync('/dev/stdin').toString().trim().split('\n').map(num => parseInt(num));
input.shift();
const countArr = Array(100001).fill(0);
const sorted = Array(input.length);

input.forEach(v=>{
    countArr[v-1]++;
});

for(let i=1;i<=10001;i++){
    countArr[i] = countArr[i-1] + countArr[i];
}

function countingSort(arr) {
    while(input.length){
        let elem = arr.pop();
        sorted[countArr[elem-1]-1] = elem;
        countArr[elem-1]--;
    }
}

countingSort(input);
console.log(sorted.join('\n'));

결과는 메모리 초과였다

합병 정렬때 처럼 수박 겉 핥기 식으로 구현한게 아닐까? 해서 생각을 해 봤다

정렬해야할 숫자가 10000보다작거나 같다고 해서 수를 카운트해서 저장할 배열의 크기를 10001로 해놨는데 이게 데이터 낭비가 너무 큰 것 같았다

두번째

const input = require('fs').readFileSync('/dev/stdin').toString().trim().split('\n').map(num => parseInt(num));
input.shift();
let countArr = [];
const sorted = Array(input.length);

input.forEach(value=>{
    // 자연수를 0에 포함하지 않기때문에 배열의 첫칸을 채우기 위한 작업
    let v = value-1;
    // 정렬할 배열의 숫자를 카운팅 단, 카운팅할 숫자가 없다면 그 인덱스의 값은 0이아닌 empty 가 됨
    countArr[v] ? countArr[v]++ : countArr[v] = 1;
});

for(let i=1; i<countArr.length;i++){
    // 카운팅 배열에 누계 합을 구하는 과정   배열의 값이 empty일 때 0으로 초기화 시켜줌
    countArr[i] = countArr[i-1] + (countArr[i] || 0);
}

function countingSort(arr) {
    while(input.length){
        //마찬가지로 배열의 첫칸을 위해 인덱스 -1
        let elem = arr.pop()-1;

        // sorted 도 마찬가지로 인덱스-1 들어가는 값은 다시 +1
        sorted[countArr[elem]-1] = elem + 1;
        countArr[elem]--;
    }
}
countingSort(input);
console.log(sorted.join('\n'));

수를 카운트 할 배열을 미리 초기화하지 않고 누적 값을 저장하면서 배열 크기를 유동적으로 만들려했으나 실패..

세번째

const input= [5,5,2,3,1,4,2,3,5,1,7];
// const input = require('fs').readFileSync('/dev/stdin').toString().trim().split('\n').map(num => parseInt(num));

input.shift();
let max = 0;

input.forEach(v=>{
    max = (max < v) ? v : max;
});

let countArr = Array(max).fill(0);
const sorted = Array(max).fill(0);

input.forEach(value=>{
    // 자연수를 0에 포함하지 않기때문에 배열의 첫칸을 채우기 위한 작업
    let v = value-1;
    // 정렬할 배열의 숫자를 카운팅
    countArr[v] ? countArr[v]++ : countArr[v] = 1;
});

for(let i=1; i<countArr.length;i++){
    // 카운팅 배열에 누계 합을 구하는 과정
    countArr[i] = countArr[i-1] + countArr[i];
}

function countingSort(arr) {
    while(input.length){
        //마찬가지로 배열의 첫칸을 위해 인덱스 -1
        let elem = arr.pop()-1;

        // sorted 도 마찬가지로 인덱스-1 들어가는 값은 다시 +1
        sorted[countArr[elem]-1] = elem + 1;
        countArr[elem]--;
    }
}
countingSort(input);
console.log(sorted.join('\n'));

그래서 생각한게 혹시 배열을 미리 초기화하지 않고 인덱스로 접근하는게 더 속도가 느린가? 싶어서

인풋 배열에서 최대값을 탐색한 후 맥스값을 이용해서 배열의 크리를 미리 할당했으나 실패..

포기

내 실력으론 무리겠다 싶어서 다른 사람의 코드를 보고 배우려고 했는데..

아마 노드로는 정해진 시간안에 풀 수 없는 듯 하다