# [Gold IV] 열 정렬정렬 정 [문제 링크](https://www.acmicpc.net/problem/25577) ## 문제 설명 <p>열정이 가득한 김정렬은 항상 배열을 오름차순 정렬하려고 하는 강박증이 있다.</p> <p>하지만 너무 열정적으로 정렬한 나머지 제대로 정렬하지 못하는 경우가 생긴다.</p> <p>김정렬의 친구로서, 정렬이가 눈치채기 전에 다시 정렬시켜주려고 한다. 하지만 배열을 너무 많이 바꿀 경우 정렬이가 눈치를 채게 되고, 정렬이는 낙담할 것이다.</p> <p>우리가 배열에 적용할 수 있는 연산은 임의의 두 값을 뽑아서 서로 교환하는 것이다. 정렬이 몰래 정렬하기 위해 최소한으로 필요한 연산 횟수를 구하자.</p> ## 입력 <p>첫 번째 줄에 배열의 크기 $N(4 ≤ N​ ≤ 100\,000)$이 주어진다.</p> <p>그다음 줄에 배열의 원소 $A_1, A_2, \cdots, A_n (-10^9 ≤ A_i ≤ 10^9, i \neq j $ 이면 $ A_i \neq A_j )$ 이 주어진다.</p> <p>배열의 원소는 모두 정수이다.</p> ## 출력 <p>배열에 적용할 최소 연산 횟수를 출력한다.</p> ## 풀이 #### 각각의 수를 인덱스와 함께 저장하고, 정렬하여 직접 빠르게 스왑해보고 최소 연산 횟수를 찾으면 된다. ``` c++ #include<bits/stdc++.h> using namespace std; int main() { ios::sync_with_stdio(0); cin.tie(0); int n; cin >> n; vector<pair<int, int>> arr(n); // {val, idx} for(int i=0;i<n;i++) { cin >> arr[i].first; arr[i].second = i; } sort(arr.begin(), arr.end()); int cnt=0; for(int i=0;i<n;i++) { while(arr[i].second!=i) { swap(arr[i], arr[arr[i].second]); cnt++; } } cout << cnt; } ```