문제 4

수 정렬하기 2

태그 보기

정렬

길이가 $N$인 정수 수열 $A_1, A_2, \cdots, A_N$이 주어진다.

수열 $A$를 오름차순으로 정렬하여 출력하라.

입력

첫 번째 줄에 정수 $N$이 주어진다. $(1 \le N \le 10^6)$

두 번째 줄에 $N$개의 정수 $A_1, A_2, \cdots, A_N$이 공백으로 구분되어 주어진다. $(1 \le A_i \le 10^9)$

첫 번째 줄에 수열 $A$를 오름차순으로 정렬하여 공백으로 구분해 출력한다.

5
3 4 2 1 5

1 2 3 4 5

$N$이 최대 $10^6$이므로 모든 원소 쌍을 비교하는 $O(N^2)$ 정렬 대신 $O(N\log(N+1))$ 비교 정렬을 사용한다. 값의 범위가 넓으므로 값마다 공간을 잡기보다 실제 원소들을 저장해 정렬하는 편이 적절하다.

정렬한 수열을 앞에서부터 출력한다. 같은 값이 여러 번 나오면 모두 출력한다.

시간복잡도는 $O(N\log(N+1))$, 배열을 저장하는 공간복잡도는 $O(N)$이다.

C++에서는 vector<int>와 sort를 사용한다. 입력·출력량이 크므로 스트림 동기화와 입력 스트림의 묶음을 해제하고, 매번 출력을 비우는 endl 대신 \n을 사용한다.

malloc으로 할당한 int 배열에 백만 개의 정수를 저장하고 qsort로 정렬한다. 입력·출력에는 버퍼를 사용한다. 각 원소는 int에 들어간다.

sys.stdin.buffer로 입력을 읽어 정수 리스트를 만들고 sort()로 정렬한다. 출력량이 크므로 정렬한 값들을 문자열로 묶어 출력한다.

int[]와 Arrays.sort를 사용한다. 입력·출력량이 크므로 BufferedInputStream에서 정수를 읽고 BufferedWriter로 출력한다.

입력 버퍼에 split_whitespace()를 적용하여 정수를 읽는다. Vec<i32>를 sort_unstable()로 정렬하고 BufWriter로 출력한다.

백만 개의 값은 Int32Array(n)에 저장해 기본 sort()로 정렬할 수 있다. 일반 Array의 기본 정렬과 달리 TypedArray의 기본 정렬은 숫자 순서이다. 원소는 $10^9$ 이하이므로 부호 있는 32비트 칸에 들어간다.

입력을 바이트 버퍼에서 읽으며 배열을 채우면 토큰 문자열을 따로 저장하는 메모리를 줄일 수 있다. 출력은 일정 개수씩 모아 process.stdout.write 또는 fs.writeSync(1, ...)로 쓴다.

언어