[JS] 10989

const fs = require('fs');
const path = process.platform === 'linux' ? '/dev/stdin' : './data.txt';

const input = fs
  .readFileSync(path)
  .toString()
  .trim()
  .split('\n')
  .map((x) => parseInt(x));
const count = input.shift();

const solve = (input) => {
  const countingArr = new Array(10000 + 1).fill(0); // 가장 큰 숫자가 10000이기 때문에 10000을 인덱스로 갖는 카운팅 배열 생성

  input.forEach((num) => {
    countingArr[num]++;
  });

  let answer = new String();

  for (let i = 0; i < countingArr.length; i++) {
    if (countingArr[i] != 0) {
      for (let j = 0; j < countingArr[i]; j++) {
        answer += i + '\n';
      }
    }
  }
  return answer.trim();
};

console.log(solve(input));

 

백준

 

2번째 문제에서 언어마다 내장된 정렬 함수(사실상 가장 성능이 좋은)를 사용했는데, 3번은 어떻게 더 빠르게 하는건가 싶었다.

 

Javascript의 경우엔, 백준에서 메모리를 늘려주지 않는 한 메모리 초과가 나오는데, 이 문제의 요구는 카운팅 정렬을 사용하는 것

카운팅 정렬은 우리가 숫자를 정렬할 때, 가장 큰 값을 알고있다면 유리한 방법이다.

(문제에서도 조건이 '10000보다 작거나 같은 자연수'이기 때문에 가능한 방법)

 

가장 큰 수만큼의 인덱스를 갖는 카운팅배열(index : 원래 배열에서의 숫자, value : 원래 배열에서의 숫자의 개수)을 만들어준다.

이후 카운팅 배열이 0이 아닐 때, 카운팅 배열의 value 만큼 index를 새로운 배열에 push하든 위처럼 빈 문자열에 더해주든 순서대로 더한다.

그러면 짜잔~ 정렬이 되어있다.

 

이런 알고리즘이나 자료구조 등은 알면 알수록 재미있고 신기하다.

어떻게든 시간복잡도나 메모리(공간 복잡도) 사이에서의 극한의 이득을 얻으려는 역사가 보인다ㅋㅋㅋㅋㅋ