k-정렬
면접 대비시간 제한2초메모리 제한256 MB
배열과 고정된 간격 k가 주어질 때, 정확히 k칸 떨어진 원소끼리만 교환해서 배열을 오름차순으로 정렬하는 최소 교환 횟수를 구하고, 불가능하면 -1을 출력한다.
문제
정렬 문제란 주어진 수 배열(또는 다른 객체)을 오름차순이나 내림차순으로 나열하는 것이다. 이 문제에는 여러 가지 변형이 있고, 그중 상당수에는 효율적인 알고리즘이 존재한다. 이런 알고리즘의 중요한 파라미터 중 하나는 배열을 정렬하는 데 필요한 원소 교환 횟수이다.
앞으로 우리는 k-정렬이라고 부를 정렬 변형을 살펴본다. 이 변형에서는 한 번의 연산(k-교환이라고 부른다)으로 번호가 정확히 k만큼 차이 나는 두 원소의 값을 서로 바꿀 수 있다. 예를 들어 초기 배열이 [6, 10, 4, 1, 2]이고 k = 3이면, 이 배열은 두 번의 연산으로 오름차순으로 정렬할 수 있다. 첫 번째 교환 후 배열은 [1, 10, 4, 6, 2]가 되고, 두 번째 교환 후에는 [1, 2, 4, 6, 10]이 된다.
정수 배열 a1, ..., an이 주어진다. 이 배열을 비내림차순으로 정렬하는 데 필요한 최소 k-교환 횟수를 구하는 것이 문제이다.
입력
첫째 줄에는 정수 n이 주어진다 (1 ≤ n ≤ 300). 둘째 줄에는 n개의 정수 a1, ..., an이 주어진다 (1 ≤ ai ≤ 109, i는 1부터 n까지). 셋째 줄에는 정수 k가 주어진다 (1 ≤ k ≤ n - 1).
출력
주어진 배열을 설명한 종류의 연산으로 비내림차순으로 정렬할 수 있으면, 정렬에 필요한 최소 k-교환 횟수를 출력한다. 그렇지 않으면 -1을 출력한다.