수 정렬하기 3

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

입력

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

출력

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

예제 입력 1

10
5
2
3
1
4
2
3
5
1
7

예제 출력 1

1
1
2
2
3
3
4
5
5
7

정답

이 문제는 Node.js로는 메모리 초과 문제를 해결할 수가 없었다. 처음엔 sort함수를 사용했다가, 메모리 초과가 발생하여 복잡도가 N인 매우 빠른 알고리즘인 Counting Sort 알고리즘을 사용하고, fs모듈을 사용했음에도 불구하고 메모리 초과를 해결할 수 없었다. 다음은 내가 생각하는 가장 간단한 코드이어서 첨부한다.

const fs = require("fs"); // Node.js의 파일 시스템 모듈을 가져옵니다.

// 입력값을 받아오는 코드입니다. 입력은 줄바꿈('\n')을 기준으로 split 하여 배열로 저장합니다.
const input = fs.readFileSync("/dev/stdin").toString().trim().split("\n");

const n = Number(input[0]); // 첫 번째 입력값은 정렬할 숫자들의 개수입니다.

// Counting sort 알고리즘에 사용할 배열을 선언합니다. 이 때 숫자의 범위는 1 ~ 10000이므로 배열의 크기를 10001로 설정합니다.
let count = Array(10001).fill(0);

// 입력받은 숫자들을 하나씩 확인하면서 해당 숫자의 개수를 세는 코드입니다.
for (let i = 1; i <= n; i++) {
  count[Number(input[i])]++;
}

// 출력할 결과를 저장할 변수를 선언합니다.
let output = "";

// 숫자 1 ~ 10000까지의 개수를 확인하여 결과 문자열을 만드는 코드입니다.
for (let i = 1; i <= 10000; i++) {
  // 숫자 i가 등장한 횟수만큼 숫자 i를 결과 문자열에 추가합니다. 이때 숫자는 개행 문자('\n')로 구분됩니다.
  output += `${i}\n`.repeat(count[i]);
}

console.log(output); // 결과를 출력하는 코드입니다.