[Rust로 백준 하루 하나] 13-11. 좌표 압축

문제 (18870번)

수직선 위에 N개의 좌표 X1, X2, ..., XN이 있다. 이 좌표에 좌표 압축을 적용하려고 한다.

 

Xi를 좌표 압축한 결과 X'i의 값은 Xi > Xj를 만족하는 서로 다른 좌표 Xj의 개수와 같아야 한다.

 

X1, X2, ..., XN에 좌표 압축을 적용한 결과 X'1, X'2, ..., X'N를 출력해보자.

 

입력

첫째 줄에 N이 주어진다.

 

둘째 줄에는 공백 한 칸으로 구분된 X1, X2, ..., XN이 주어진다.

 

출력

첫째 줄에 X'1, X'2, ..., X'N을 공백 한 칸으로 구분해서 출력한다.

 

제한

• 1 ≤ N ≤ 1,000,000
• -109 ≤ Xi ≤ 109

---

풀이

코드

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

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

    let mut n = String::new();
    reader.read_line(&mut n).unwrap();
    let n: usize = n.trim().parse().unwrap();

    let mut input = String::new();
    reader.read_line(&mut input).unwrap();
    let input: Vec<i32> = input
        .trim()
        .split_whitespace()
        .map(|i| i.parse().unwrap())
        .collect();

    // input의 정렬된 중복 제거된 복사본 생성
    let mut sorted_input = input.clone();
    sorted_input.sort();
    sorted_input.dedup();

    // 해시맵을 사용하여 각 값에 대해 압축된 인덱스를 저장
    let mut index_map = HashMap::new();
    for (i, &value) in sorted_input.iter().enumerate() {
        index_map.insert(value, i);
    }

    // 압축된 결과 출력
    for &value in &input {
        let result = index_map[&value];
        write!(writer, "{} ", result).unwrap();
    }
}

해설

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

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

    let mut n = String::new();
    reader.read_line(&mut n).unwrap();
    let n: usize = n.trim().parse().unwrap();

    let mut input = String::new();
    reader.read_line(&mut input).unwrap();
    let input: Vec<i32> = input
        .trim()
        .split_whitespace()
        .map(|i| i.parse::<i32>().unwrap())
        .collect();
    let mut input_for_index = input.clone();
    input_for_index.sort();
    input_for_index.dedup();

    let mut writer = BufWriter::new(io::stdout().lock());
    for i in 0..n {
        let result = input_for_index
            .iter()
            .position(|&x| x == input[i]).unwrap();
        write!(writer, "{} ", result).unwrap();
    }
}

이렇게 풀어서 답은 제대로 나왔었는데 시간초과로 실패하였습니다.

 

.position()을 사용하여 각 좌표에 대해 선형 탐색을 수행하기 때문입니다. 이로 인해 최종 시간 복잡도는 O(N^2)가 되어 입력 크기가 클 때 매우 느려집니다.

 

이 문제를 해결하기 위해 좌표 압축의 효율성을 높여야 합니다. 대신 해시맵을 사용하여 좌표 값에 해당하는 압축된 인덱스를 빠르게 찾을 수 있도록 하겠습니다. 이렇게 하면 시간 복잡도를 O(N log N)으로 줄일 수 있습니다.

---

추가 학습

• 특이사항 없음