백준 10972 다음 순열

순열은 순서가 부여된 임의의 집합을 다른 순서로 뒤섞는 연산이다.

다음 순서의 순열을 찾으려면 c++에서는 next_permutation과 prev_permutation이 존재하기 때문에 사용하면 된다.

 

직접 구현하기 위한 방법은 아래와 같다.

1. A[i-1] < A[i]를 만족하는 가장 큰 i를 찾는다.(이 말은 i-1 index 이후의 순열은 내림차순으로 정렬되어 있다는 말이다.)

2. j>=i 이면서 A[j] > A[i-1] 를 만족하는 가장 큰 j를 찾는다.(다음 순열은 순열을 하나의 수로 봤을 때 더 큰 수가 되어야 하므로, A[i-1]보다 큰 수를 앞으로 가져와야 한다. 작은 수를 앞으로 가져오는 것은 작은 수로 바꾸는 것이기 때문이다.)

3. A[i-1]과 A[j]를 swap한다.

4. A[i]부터 순열을 뒤집는다.(i-1 index 이후는 내림차순이기 때문에 오름차순으로 정렬하기 위해 순열을 swap하여 뒤집어 준다.)

 

순열 2317645을 예시로 들겠다.

처음에는 2<3이고 3<1이기 때문에 i를 1이라고 생각했다. 하지만 조건을 만족하는 가장 큰 i이기 때문에 

4<5도 조건을 만족하게 되어 i는 6이 된다. 따라서 j는 6이 되고, 4와 5를 swap하게 된다. 4번 과정에 해당되는 것이 없기 때문에 2317645의 다음 순열은 2317654가 된다.

 

만약 2317654의 다음 순열을 구한다면, 1<7일 때 가장 큰 i가 나오게 된다. 따라서 i는 3이 된다. 

A[i-1]의 값은 1이 되고, i+1의 인덱스부터 끝까지 탐색하면서 A[j] > A[i-1]을 만족하는 j를 찾는다. 결과적으로 j는 6이 되고, 1과 4를 swap하게 된다. 2317654 => 2347651이 된다. 

마지막으로 4번 과정을 거치면 2341567이 된다.

즉, 2317654의 다음 순열은 2341567이 되는 것이다.

 

마지막 예시는 7236541이다.

i는 3이고, A[i-1]은 3이다. j는 5가 되고 A[j]는 4가 된다. 따라서 3과 4를 swap하고, A[i]부터 순열을 뒤집는다.

결과적으로 7236541의 다음 순열은 7241356이 된다.

 

1번 과정에서 O(N)

2번 과정에서 O(N)

3번 과정에서 O(1)

4번 과정에서 O(N) 이다.

각각 독립적이므로 총 시간 복잡도는 O(N)이다.

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int main() {
    int n;
    cin >> n;
    vector<int> a(n);
    for (int i=0; i<n; i++) {
        cin >> a[i];
    }
    if (next_permutation(a.begin(),a.end())) {
        for (int i=0; i<n; i++) {
            cout << a[i] << ' ';
        }
    } else {
        cout << "-1";
    }
    cout << '\n';
    return 0;
}

------------------------------------------------------------------------------------------------------------------------------

다음 순열을 구하는데 필요한 시간 복잡도는 N * N!이다. 순열을 구하는데 N!이 필요하고, 다음 순열 계산을 위해 N이 필요하기 때문이다. N * N!이 1억이 넘지 않게 하려면 N은 최대 10이 될 수 있다.

따라서 순열을 구하는 문제에서 N의 크기가 어떻게 되는지 알아야 한다.

• 3! = 6
• 4! = 24
• 5! = 120
• 6! = 720
• 7! = 5,040
• 8! = 40,320
• 9! = 362,880
• 10! = 3,628,800
• 11! = 39,916,800