문제 5
수 정렬하기 3
길이가 $N$인 정수 수열 $A_1, A_2, \cdots, A_N$이 주어진다.
수열 $A$를 오름차순으로 정렬하여 출력하라.
입력
첫 번째 줄에 정수 $N$이 주어진다. $(1 \le N \le 10^7)$
두 번째 줄에 $N$개의 정수 $A_1, A_2, \cdots, A_N$이 공백으로 구분되어 주어진다. $(1 \le A_i \le 100\,000)$
출력
첫 번째 줄에 수열 $A$를 오름차순으로 정렬하여 공백으로 구분해 출력한다.
예제 입력 1
5 3 4 2 1 5
예제 출력 1
1 2 3 4 5
공식 해설
원소는 최대 $10^7$개이지만 가능한 값은 $1$부터 $100\,000$까지이다. 각 원소를 따로 정렬하지 말고 값별 등장 횟수를 세자.
빈도 배열을 $0$으로 초기화하고, 수 $x$를 읽을 때마다 $x$의 빈도를 $1$ 늘린다. 입력을 모두 읽으면 작은 값부터 등장 횟수만큼 출력한다. 각 값을 원래 개수대로 출력하며 값이 감소하지 않으므로 요구한 정렬 결과와 같다.
수열 전체를 저장할 필요는 없다. 값의 상한을 $U=100\,000$이라 하면 시간복잡도는 $O(N+U)$, 공간복잡도는 $O(U)$이다.
구현 · 언어별 풀이
C++ 구현
vector<int> count(100001)에 입력을 읽는 즉시 빈도를 누적한다. 입출력량이 크므로 빠른 입출력을 사용하고, 출력도 일정량씩 묶어 쓴다.
C 구현
크기가 $100\,001$인 int 빈도 배열만 둔다. 입력은 fread 버퍼에서 정수 단위로 읽어 즉시 빈도를 올린다. 출력 버퍼를 주기적으로 비워 천만 개의 원소를 다시 저장하지 않는다.
Python 구현
빈도 배열에 입력을 바로 누적한다. 둘째 줄 전체를 split()하면 천만 개의 토큰이 생기므로 고정 크기 바이트 청크에서 정수를 읽고, 청크 경계에 걸린 토큰을 이어 처리한다. 출력도 제한된 크기로 묶는다.
Java 구현
int[100001]에 빈도만 저장하고 BufferedInputStream에서 값을 하나씩 읽는다. 출력은 BufferedWriter에 값을 반복해서 써서 결과 전체를 메모리에 모으지 않는다.
Rust 구현
빈도는 Vec<u32>로 충분하다. BufRead 또는 고정 크기 읽기 버퍼에서 숫자를 이어 파싱하고 즉시 빈도를 갱신한다. BufWriter로 출력하여 전체 입력·출력 문자열을 함께 보관하지 않는다.
JavaScript 구현
길이 $100\,001$의 Int32Array에 빈도를 누적한다. 빈도는 최대 $10^7$이므로 32비트 정수로 충분하다. 입력값 전체를 split()한 뒤 저장하면 천만 개의 문자열 객체가 생기므로 이 문제에서는 피한다.
fs.readSync(0, buffer, ...)로 고정 크기 Buffer를 반복해서 읽고, 숫자를 만드는 누적값을 다음 청크까지 유지한다. 공백을 만날 때 첫 숫자는 $N$으로 읽고 이후 숫자는 빈도에 반영한다. 마지막 숫자 뒤에 공백이 없는 경우도 처리한다. 이렇게 하면 청크 경계에서 숫자가 끊겨도 올바르게 읽는다.
작은 값부터 빈도만큼 출력하되 출력 문자열도 고정 크기로 모아 fs.writeSync(1, ...)로 비운다. 수열 전체나 전체 답을 보관하지 않아 공통 풀이의 $O(U)$ 공간을 유지한다.