[Rust로 백준 하루 하나] 13-4. 수 정렬하기 2

문제 (2751번)

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

입력

첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 절댓값이 1,000,000보다 작거나 같은 정수이다. 수는 중복되지 않는다.

출력

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

---

풀이

코드

use std::io::{self, BufRead, BufReader, BufWriter, Write};

fn main() {
    let mut reader = BufReader::new(io::stdin().lock());

    let mut buffer = String::new();
    reader.read_line(&mut buffer).unwrap();
    let n: usize = buffer.trim().parse().unwrap();
    
    let mut numbers = Vec::with_capacity(n);
    for _ in 0..n {
        buffer.clear();
        reader.read_line(&mut buffer).unwrap();
        let number: i32 = buffer.trim().parse().unwrap();
        numbers.push(number);
    }
    numbers.sort();
    
    let stdout = std::io::stdout();
    let mut writer = BufWriter::new(stdout.lock());
    for number in numbers {
        writeln!(writer, "{}", number).unwrap();
    }
}

해설

This sort is stable (i.e., does not reorder equal elements) and O(n * log(n)) worst-case.

https://doc.rust-lang.org/std/vec/struct.Vec.html#method.sort
rust에서 sort 메서드는 기본적으로 Timsort 구현으로 안정적이며(즉, 같은 요소를 재정렬하지 않음) 최악의 경우 $O(n*log(n))$의 시간복잡도를 갖기 때문에 문제가 없습니다. 그런데 기존 입출력 방식으로 풀면 Vec::with_capacity()를 써도 계속 시간초과 메시지가 뜨게 됩니다.

따라서 입출력 방식을 빠른 입출력으로 바꾸었더니 해결할 수 있었습니다.

---

추가 학습

• 특이사항 없음