[1071] 소트

https://www.acmicpc.net/problem/1071

1071번: 소트

<문제>

결론적으로 nlogn에 풀렸는데, n이 50으로 엄청 작아서 의아하다. 백트래킹으로 풀리는지는 잘 모르겠다...

n이 이 문제보다 큰 100이어도 가지치기를 통해 백트래킹이 돌아갔던 문제가 하나 있는데,

"[6590] 덧셈 체인" 처럼 백트래킹이 될 것이란 확신을 갖기 쉽지 않다.

 

이 문제는 두가지가 풀이를 구상하는 데에 꽤나 큰 힌트가 되었다.

첫번째는 "사전 순으로 가장 앞서는.."의 조건이고

두번째는 예제 2에서 볼 수 있듯이, 마치 두 개의 그룹{{1 1 1 1}, {2 2 2 2 2}}이 swap하듯 정답 수열을 만드는 경우다.

 

두번째부터 살펴보면, 이렇게 "그룹간 swap"하는 듯한 형태는 항상 {(두번째로 큰 수), (첫번째로 큰 수)}에서만 일어난다.

이는 예제 2나 예제 5를 중점적으로 살피다 보면 쉽게 관찰할 수 있겠다.

 

첫번째였던 "사전 순"의 조건을 만족하기 위해서는, 입력을 우선 정렬해줄 필요가 있겠다. 

내림차순 정렬된 수열은 항상 조건을 만족하지만, "사전 순"의 조건에서 가장 최적해에서 멀다.

오름차순 정렬된 수열은 조건을 만족할지는 알 수 없지만, "사전순"의 조건에서 가장 가깝다.

그렇기에 오름차순 정렬된 상태에서, 버블소트를 하듯이 진행하되

조건을 만족하는, 곧 v[i]+1 != v[i+1]인 경우는 그냥 skip해주었다.

v[i] + 1  == v[i + 1]인 경우에는, 'v[i]+2'를 찾아서, v[i]와 v[i]+2를 swap해주었다.

만약 v[i]+2^[각주:1]가 존재하지 않는다면, v[i]와 v[i+1]은 곧 {(두 번째로 큰 수), (첫 번째로 큰 수)}라는 의미이므로 

그룹으로 swap해주었다.

 

<소스코드>

#include <bits/stdc++.h>
using namespace std;
int n, cnt;
vector<int> v;
int main(void) {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> n;
    v.resize(n);
    int i;
    for (i = 0; i < n; i++) cin >> v[i];
    sort(v.begin(), v.end());
 
    for (i = 0; i + 1 < n; i++) {
        if (v[i] + 1 == v[i + 1]) {
            auto it = lower_bound(v.begin() + i, v.end(), v[i] + 2);
            if (it != v.end()) {
                int idx = it - v.begin();
                swap(v[i + 1], v[idx]);
            } else {
                int r = n - 1;
                int l =
                    lower_bound(v.begin() + i - cnt, v.end(), v[i]) - v.begin();
                while (l < r) {
                    swap(v[l], v[r]);
                    l++, r--;
                }
            }
            cnt = 0;
        } else if (v[i] == v[i + 1])
            cnt++;
    }
 
    for (auto& i : v) cout << i << " ";
    return 0;
}

 

1. 정확히는 v[i]+2 이상의 수 [본문으로]