백준 15594 Out of Place (USACO January 2018 Bronze 3번)

문제 링크: https://www.acmicpc.net/problem/15594

15594번: Out of Place

먼저 숫자들을 bef, aft 두 배열에 입력받은후, aft 배열만 sort함으로써, bef 배열을 aft 배열과 최소의 swap으로 똑같이 만드는게 목표임. 앞에서부터 훑으면서, aft 배열과 bef 배열에 있는 숫자가 같으면 continue로 넘어가고, 다르면 swap할 적당한 숫자를 찾아야함. swap 해야할 숫자의 index에서 aft와 bef 배열에 있는 숫자가 같으면 swap할 필요가 전혀 없다는것을 주의해야함.

#include <bits/stdc++.h>
using namespace std;
 
int N, bef[101], aft[101];
 
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
 
    cin >> N;
    for(int i = 0; i < N; i++) {
        cin >> bef[i];
        aft[i] = bef[i];
    }
    sort(aft, aft + N);
 
    int ans = 0;
    for(int i = 0; i < N; i++) {
        if(aft[i] == bef[i]) continue;
        for(int j = i; j < N; j++) {
           if(aft[i] == bef[j] && aft[j] != bef[j]) {
                swap(bef[i], bef[j]);
                ans++;
           }
        }
    }
 
    cout << ans << '\n';
    return 0;
}