정렬 문제
면접 대비시간 제한3초메모리 제한1024 MB
1부터 n까지의 순열이 주어지고, 값이 1만큼 차이나는 두 원소만 교환할 수 있을 때 배열을 오름차순으로 정렬하는 최소 교환 횟수를 구한다.
문제
배열 [p[1], p[2], ..., p[n]]이 주어진다. 배열의 모든 수는 서로 다르고, 1 이상 n 이하의 양의 정수다. 배열에 다음 연산만 할 수 있다. |p[x]−p[y]| = 1인 두 인덱스 x와 y를 골라 p[x]와 p[y]의 값을 교환한다. 이 배열을 오름차순으로 정렬하려고 한다. 즉, 모든 i ∈ {1, 2, ..., n}에 대해 p[i] = i가 되게 하려고 한다. 예를 들어 배열 [p[1] = 2, p[2] = 3, p[3] = 1]은 두 번의 연산으로 정렬할 수 있다.
- p[1]과 p[3]을 교환한다. 배열은 [p[1] = 1, p[2] = 3, p[3] = 2]가 된다.
- p[2]와 p[3]을 교환한다. 배열은 [p[1] = 1, p[2] = 2, p[3] = 3]이 되어 오름차순으로 정렬된다.
주어진 배열을 오름차순으로 정렬하는 최소 연산 횟수를 구하는 프로그램을 작성하시오.
입력
입력은 두 줄로 이루어진다. 첫째 줄에는 정수 n이 주어진다. 둘째 줄에는 배열 [p[1], p[2], ..., p[n]]을 나타내는 n개의 수 p[1], p[2], ..., p[n]이 공백으로 구분되어 주어진다.
출력
주어진 배열을 정렬하는 데 필요한 최소 연산 횟수를 나타내는 수 하나만 출력한다.
제한
- 1 < n ≤ 200000.
- 1 ≤ p[i] ≤ n.
- 모든 p[i]는 서로 다르다.