A를 가장 최대한 큰 덩어리로 나누어 A를 정렬하는 문제입니다.
우선 k = 3인 경우는 항상 A가 정렬 가능함을 알 수 있습니다.
배열에서 최댓값을 찾아 [ … ] [ 최댓값 ] [ … ] 조각으로 나눈 뒤, 최댓값을 맨 앞으로 보내는 작업을 $N$번 반복하면 되기 때문입니다.
다음으로 k = 2인 경우가 어디에 속하는지를 확인해야 합니다.
두 조각으로 잘랐을 경우에 재배열하는 경우는 배열을 특정한 원소 기준으로 회전한 경우와 같습니다.
따라서 최솟값이 위치한 인덱스 $i$부터 인덱스 $(i + N) \bmod N$까지 순회하며 정렬이 되었는지 확인하면 됩니다.
참고
Rust의 std::iter::is_sorted
는 아직 experimental입니다…
코드
fn solve(nums: &[u32]) -> u32 {
let mut min = std::u32::MAX;
let mut min_pos = 0;
for (i, &num) in nums.iter().enumerate() {
if min > num {
min = num;
min_pos = i;
}
}
let mut prev = 0;
let is_sorted = nums
.iter()
.cycle()
.skip(min_pos)
.take(nums.len())
.all(|&v| {
let cond = prev < v;
prev = v;
cond
});
if is_sorted {
if min_pos == 0 {
1
} else {
2
}
} else {
3
}
}