C++ 10972 다음 순열

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

10972번: 다음 순열

 

처음에는 브루트포스로 모든 순열을 순서대로 조사한 후 같은 순열이 나오면 그 다음 순열을 출력하는 방식으로 풀이하였다.

#include <bits/stdc++.h>
using namespace std;
int n;
bool vis[10001];
int arr[10001];
int sortedArr[10001];
vector<int> vec;
bool flag;

void dfs(int k) {
    if(k == n) {
        if(flag) {
            for (const auto &v: vec) {
                cout << v << ' ';
            }
            exit(0);
        }

        for(int i=0; i<n; i++) {
            if(arr[i] != vec[i])
                return;
        }
        flag = true;
        return;
    }

    for(int i=0; i<n; i++) {
        if(vis[sortedArr[i]]) continue;
        vis[sortedArr[i]] = true;
        vec.push_back(sortedArr[i]);
        dfs(k+1);
        vis[sortedArr[i]] = false;
        vec.pop_back();
    }
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> n;
    for(int i=0; i<n; i++) {
        cin >> arr[i];
        sortedArr[i] = arr[i];
    }
    sort(sortedArr, sortedArr+n);
    dfs(0);
    cout << -1;
}

당연히 이렇게 풀면 O(n!)이므로 시간 초과가 뜬다. 하지만 다른 방법이 생각나지 않았다.

 

다음과 같이 순열을 나열하는 규칙을 이용하여 풀 수 있다.

풀이

1. 뒤에서부터 시작하여 오름차순이 끊기는 지점 찾기

2. 끊기는 지점 뒤에서, 끊기는 지점보다 처음으로 큰 원소를 찾아서 교환

3. 끊기는 지점 뒤의 원소의 순서를 바꿔 준다.

 

예시를 들면 다음과 같다.

결과적으로 1 2 3 6 5 4의 다음 순열은 1 2 4 3 5 6이 된다.

코드

#include <bits/stdc++.h>
using namespace std;
int n;
int arr[10001];

bool next_permutation() {
    int i = n-1;
    while(i > 0 && arr[i-1] > arr[i]) {
        i--;
    }
    if(i == 0) {
        return false;
    }
    int j = n-1;
    while(i-1 < j && arr[i-1] > arr[j])    j--;
    swap(arr[i-1], arr[j]);

    j = n-1;
    while(j > i) {
        swap(arr[i], arr[j]);
        i++;
        j--;
    }
    return true;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> n;
    for (int i = 0; i < n; i++)
        cin >> arr[i];

    if (next_permutation()) {
        for (int i = 0; i < n; i++) {
            cout << arr[i] << ' ';
        }
    }
    else{
        cout << -1;
    }
}

시간 복잡도는 O(N)

 

참고로 STL next_permutation이라는게 존재해서 배열의 시작주소와 끝 주소를 넣어주면, 다음 순열을 찾아준다.

#include <bits/stdc++.h>
using namespace std;
int n;
int arr[10001];

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> n;
    for (int i = 0; i < n; i++)
        cin >> arr[i];

    if (next_permutation(arr, arr+n)) {
        for (int i = 0; i < n; i++) {
            cout << arr[i] << ' ';
        }
    }
    else {
        cout << -1;
    }
}

간단하게 풀 수 있다.