[백준] 15594 Out of place

숫자가 주어질 때 오름차순으로 만들려 한다

숫자 두개를 swap 가능할 때 최소의 swap 수를 구하면 된다

입력받은 숫자를 정렬시켜서 있어야 할 자리가 맞는지 2중 for문으로 확인하고 제출했다

근데 바로 틀렸따 ㅎㅎㅎ

고민하다가 그냥 생각없이 뒤에서부터 확인하니까 답보다 1이 크게나왔다

똑같이 나올 줄 알았는데...

그래서 어떤수에서는 앞에서부터 보는거보다 뒤에서부터 보는게 작겠구나~ 

생각하고 앞에서부터 비교한 답 & 뒤에서부터 비교한 답을 비교해서 작은답을 출력하니 맞았다!

소스코드

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int n;
int check(vector<int>&a, vector<int>&b) {
    int ret = 0;
    for (int i = 0; i < n; i++) {
        if (a[i] == b[i]) continue;
        for (int j = i + 1; j < n; j++) {
            if (a[j] == b[i]) {
                swap(a[i], a[j]); ret++; break;
            }
        }
    }
    return ret;
}
int main() {
    scanf(" %d", &n);
    vector<int> a(n), b(n), c(n);
    for (int i = 0; i < n; i++) {
        scanf(" %d", &a[i]);
        b[i] = c[i] = a[i];
    }
    reverse(b.begin(), b.end());
    sort(c.begin(), c.end());
    int ans = check(a, c);
    reverse(c.begin(), c.end());
    int rans = check(b, c);
    printf("%d\n", min(ans, rans));
}