힌트
$i$번째 교환 후 $A$의 특정 범위의 값을 알 수 있습니다.
핵심 아이디어
선택 정렬은 문제 설명과 같이 최댓값을 한 번 찾고, 교환을 최대 한 번 하는 동작을 $N - 1$번만 반복합니다. 특히, $i$번째 교환에서 마지막 $i$개의 값이 모두 정렬됩니다.
이미 정렬된 배열과 뒤쪽 위치부터 비교하여 제자리에 있지 않은 값을 옮겨 주는 동작을 반복하는 식으로 문제를 해결할 수 있습니다. 먼저 각 수의 처음 위치를 각 수의 크기 순으로 배열 $S$에 저장하고, 뒤부터 탐색하면서 $S[i]$가 $i$가 아니라면 (즉 숫자가 제자리에 있지 않다면) $A$에서 $S[i]$번째 수와 i번째 수를 바꿔야 합니다. 이때 $A$에서 $S[i]$번째 수에 해당하는 $S$의 값 또한 갱신해야 하는데, 이를 위해 $M[i] = k$이면 $A[i]$가 $A$에서 $k$번째로 큰 수이도록 하는 배열 $M$을 만들어줍니다. $M$은 $S$의 인덱스와 값을 맞바꾼 배열이며, $S[M[i]]$가 $A$에서 $S[i]$번째 수에 해당하는 $S$의 값임을 알 수 있습니다. 따라서 $S[M[i]]$를 $S[i]$로 바꾸고, $A$와 $M$에서 각각 $S[i]$번째와 $i$번째 수를 교환하는 방식으로 위치를 업데이트할 수 있습니다. 선택 정렬은 $O(n^2)$ 시간복잡도를 가지지만 $O(n\log n)$ 알고리즘을 사용하여 정렬한 후, 위와 같이 제자리를 찾아가는 알고리즘을 짜면 전체 시간 $O(n \log n) + O(n) = O(n \log n)$에 문제를 해결할 수 있습니다.알고리즘
코드(23884번)
use std::io::{stdin, Read};
fn main() {
let mut input = String::new();
stdin().read_to_string(&mut input).unwrap();
let mut input = input.split_ascii_whitespace().map(str::parse).flatten();
let n = input.next().unwrap();
let mut k = input.next().unwrap();
let mut a: Vec<_> = input.take(n).collect();
let mut sorted: Vec<_> = (0..n).collect();
sorted.sort_unstable_by_key(|&i| a[i]);
let mut map = vec![0; n];
for (i, &j) in sorted.iter().enumerate() {
map[j] = i;
}
use std::fmt::Write;
let mut output = String::new();
for i in (0..n).rev() {
if sorted[i] != i {
sorted[map[i]] = sorted[i];
map.swap(sorted[i], i);
a.swap(sorted[i], i);
k -= 1;
if k == 0 {
for ai in &a {
write!(output, "{} ", ai).unwrap();
}
break;
}
}
}
if k > 0 {
println!("-1");
} else {
print!("{}", output);
}
}