[백준] 9078 – 정렬

문제

#9078: 정렬(acmicpc.net)

설명

정렬할 때 인접한 두 숫자를 이동시켜 앞이나 뒤에 삽입하는 것만으로 정렬이 가능한지 여부를 판단하는 것은 문제가 있습니다.

골드 2이지만 코드 자체는 매우 간결합니다.

이미 정렬 가능한 배열에 두 개의 추가 요소가 추가되면 해당 요소가 이미 정렬된 경우에만 전체 배열이 정렬 가능하다고 합니다.

예를 들어 배열 1 2 3 4는 이미 정렬되어 있으므로 5 6은 처음이든 마지막이든 상관없이 정렬 가능합니다. (5 6 1 2 3 4 → 5 6 뒤로 이동 → 1 2 3 4 5 6)

2 4 1 3과 같은 배열은 보시다시피 정렬할 수 없습니다. 오름차순(1씩 증가) 간격이 전혀 없기 때문입니다. 마찬가지로 1 2 4 3도 불가능합니다.

순서가 바뀌면 요소 사이의 크기 변화도 원본에서 짝수만큼 바뀌고 카운트 변수가 그 값을 나타낸다.

짝수로 바뀌는 이유에 대해서는 앞서 2개의 정렬된 요소가 들어왔다고 합니다.5 6 1 2 3 4와 같은 경우 크기 조정이 두 번 발생하도록 1 2 3 4 5 6으로 만들어야 합니다.홀수로 바뀌면 중간 어디선가 싱크가 어긋나서 다시 카운트가 늘어나지 않은 걸로 해석하시면 됩니다.

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int T;
    cin >> T;
    
    while (T--) {
        int N;
        cin >> N;
        
        vector<int> v(N);
        for (int i = 0; i < N; i++) {
            cin >> v(i);
        }
        
        int count = 0;
        for (int i = 0; i < N; i++) {
            for (int j = i + 1; j < N; j++) {
                if (v(i) > v(j)) count += 1;
            }
        }
        
        if (count % 2 == 0) cout << "YES\n";
        else cout << "NO\n";
    }
    
    return 0;
}