BOJ 1071: 소트

#include <bits/stdc++.h>
using namespace std;
typedef long double ld;
using ll = long long;
int arr[1002];
int main() {
    cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(false);
    ll n, sz, prior = -2; cin >> n; sz = n;
    vector<int> vec(n);
    for (ll i = 0; i < n; i++){
        int x; cin >> x; arr[x]++;
    }
    vector<ll> ans;
    while (sz--){
        for (int i = 0; i <= 1000; i++){
            if (arr[i] > 0){
                if (arr[i] + arr[i + 1] != sz + 1 && i != prior + 1){
                    ans.emplace_back(i); prior = i;
                    arr[i]--;
                    break;
                }
            }
        }
    }
    for (int i = 0; i <= 1000; i++){
        if (arr[i]) ans.emplace_back(i);
    }
    for (auto i: ans) cout << i << " ";
    return 0;
}

 

arr[i] + 1가 arr[i + 1]과 일치하면 안된다는 조건을 생각하면 대충 정수 (arr[i], arr[i + 1])(arr[i] + 1 = arr[i + 1])만 남는 상황일 때 arr[i + 1]을 먼저 배치하고 arr[i]를 나중에 배치하면 될 것이다. 그 외에는 먼저 나오는 숫자 순으로 하면 된다.