문제 (10989번)
N개의 수가 주어졌을 때, 이를 오름차순으로 정렬하는 프로그램을 작성하시오.
입력
첫째 줄에 수의 개수 N(1 ≤ N ≤ 10,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 10,000보다 작거나 같은 자연수이다.
출력
첫째 줄부터 N개의 줄에 오름차순으로 정렬한 결과를 한 줄에 하나씩 출력한다.
풀이
코드
use std::io::{self, BufReader, BufRead, BufWriter, Write};
fn main() {
let mut reader = BufReader::new(io::stdin().lock());
let mut writer = BufWriter::new(io::stdout().lock());
let mut n = String::new();
reader.read_line(&mut n).unwrap();
let n: usize = n.trim().parse().unwrap();
let mut counting_array: [usize; 10001] = [0; 10001];
let mut input = String::new();
for _ in 0..n {
input.clear();
reader.read_line(&mut input).unwrap();
let input: usize = input.trim().parse().unwrap();
counting_array[input] += 1;
}
for index in 0..counting_array.len() {
for _ in 0..counting_array[index] {
writeln!(writer, "{}", index).unwrap();
}
}
}해설
이 문제는 시간제한은 물론 메모리 제한이 있어 [[13-1. 수 정렬하기]], [[13-4. 수 정렬하기 2]] 처럼 단순 정렬을 해서는 문제를 풀 수 없습니다. 10,000,000개의 숫자가 주어지기 때문입니다.
이 문제의 경우, 주어지는 1천만개의 숫자가 10,000보다 작거나 같은 자연수라고 정해져있기 때문에 카운팅 정렬이 효과적일 수 있습니다.
카운팅 정렬(Counting Sort)은 입력 데이터의 범위가 제한되어 있을 때 매우 효율적인 정렬 알고리즘입니다. 이 알고리즘의 시간 복잡도는 O(N + K)로, N은 데이터 개수, K는 데이터 값의 범위를 의미합니다. 이 알고리즘은 특히 정수 정렬에 유용하며, 메모리 사용량도 매우 적절합니다.
중첩된 for 루프를 사용하고 있어, 이 부분이 시간복잡도를 증가시킬 수 있는 요소로 보일 수 있습니다. 그러나 실제로는 그렇지 않습니다. 왜냐하면 카운팅 정렬의 출력 단계에서 시간복잡도가 O(N^2)이 되지 않기 때문입니다.
왜 O(N^2)이 아닌가?
중첩된 for 루프가 있다고 해서 항상 O(N^2)이 되는 것은 아닙니다. 시간 복잡도는 전체 반복 횟수에 따라 결정됩니다. 각 반복문이 어떤 방식으로 데이터를 다루는지 고려해야 합니다.
- 첫 번째 루프 (
for i in 0..10001):- 이 루프는
counting배열의 크기인 10,001번 반복됩니다. 이 부분은 데이터 값의 범위(K)에 따라 결정됩니다.
- 이 루프는
- 두 번째 루프 (
for _ in 0..counting[i]):- 이 내부 루프는
counting[i]의 값에 따라 반복됩니다.counting[i]의 합은 입력된 전체 수의 개수, 즉 N입니다. - 내부 루프에서 모든
counting[i]의 합은 정확히 N번 반복됩니다.
- 이 내부 루프는
이 두 루프를 합치면, 최종적으로 출력 부분의 총 반복 횟수는 N입니다. 따라서 출력 단계의 시간 복잡도는 O(N)입니다.
전체 코드의 시간 복잡도
전체 코드에서의 주요 연산은 다음과 같이 구성됩니다:
- 입력을 읽고 카운트하는 단계: O(N)
- 카운팅 정렬에서의 출력 단계: O(N)
결과적으로, 이 카운팅 정렬 알고리즘의 전체 시간 복잡도는 O(N + K)이며, 여기서 K는 데이터 값의 범위입니다. 이 경우 K는 10,001로 고정되어 있기 때문에 시간 복잡도는 O(N)과 거의 동일하게 동작합니다.
추가 학습
GPT에 물어봤을 때 나온 해결책인데 어떤 상황에 쓰이는 지 등을 더 알아보도록 합시다.
-
Vec대신 정렬된 출력 사용:- 모든 수를 메모리에 저장하지 않고, 파일이나 표준 출력에 바로 출력하는 방식으로 접근할 수 있습니다. 하지만 Rust에서 이 방법은 사용하기 어렵고, 구현이 복잡할 수 있습니다.
-
External Sorting 기법 사용
- 주어진 숫자들을 모두 메모리에 저장하지 않고, 정렬된 상태로 바로 출력하는 방법입니다.
- 메모리 초과를 방지하기 위해 Rust의
BTreeSet을 활용할 수도 있습니다.BTreeSet은 내부적으로 이진 트리를 사용해 요소를 정렬된 상태로 저장하고, 메모리를 더 효율적으로 사용할 수 있습니다.
