[JS] 백준 10814번 나이순 정렬

---

문제 링크

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

풀이 전략

온라인 저지에 가입한 사람들의 나이와 이름이 가입한 순서대로 주어진다. 이때, 회원들을 나이가 증가하는 순으로, 나이가 같으면 먼저 가입한 사람이 앞에 오는 순서로 정렬하는 프로그램을 작성하시오.

=> stable하게 정렬해야 한다. 
=> 대표적인 stable sort 알고리즘인 counting sort(계수정렬)을 이용하였습니다. 

코드 

const fs = require("fs");
const input = fs.readFileSync("/dev/stdin").toString().trim().split("\n");

// counting sort.

const n = input.shift();

solution(input.map((v) => v.split(" ")));

function solution(Iarr) {
    const dedup = new Set();
    for (const [num, people] of Iarr) dedup.add([+num, people]);

    const arr = Array.from(dedup);

    let max = 0;
    for (const [num, people] of arr) if (max < num) max = num;

    const C_arr = Array.from({ length: max + 1 }, () => 0);

    arr.forEach((v) => C_arr[v[0]]++);
    C_arr.reduce((prev, cur, idx) => (C_arr[idx] = prev + cur));

    const result = Array.from({ length: arr.length }, () => 0);

    for(let i = n - 1; i >= 0; i--){
        const [num, people] = arr[i];
        result[C_arr[num] - 1] = `${num} ${people}`;
        C_arr[num]--;
    }

    console.log(result.join("\n"));
}

 

회고

도움받은 글
counting sort를 시각적으로 볼 수 있는 사이트

위의 두 글의 도움을 받아 JS로 작성하였다. counting sort는 stable 하게 정렬하고 시간복잡도도O(n)으로 상당히 빠른 속도를 가지고 있다. 누적합을 구한 배열을 보고 숫자가 어디에 위치할지 idx를 정할 수 있기 때문에 누적합 Array는 필수적이다. 하지만, 누적합을 구하기 위해 원래 구하려던 배열의 최댓값 만큼의 공간을 소모하게 된다.
만약, 배열안에 십만이 있다면 십만개의 Array를 생성하는 셈이기 때문에 메모리적으로 낭비가 심한셈이다.

따라서 counting sort는 정렬하는 숫자가 특정한 범위안에 있다면 사용하는 것이 일반적. 상황에 따라 알맞은 sort 알고리즘을 선택하는 것이 중요하다. 

메모리를 엄청나게 소모한 모습을 볼 수 있습니다.

더 좋은 방법이나 의견이 있으시다면 댓글 부탁드립니다 :)