[알고리즘 문제] 백준10792 - 다음 순열

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

10972번: 다음 순열

문제는 어떤 수열이 주어졌을 때, 그 바로 다음 순열을 구하는 문제이다.

 

그냥 next_permutation()을 사용해서 풀긴 했는데, 애초에 입력으로 숫자의 범위가 10000이다. 이는 곧, 10000!를 의미하는데 제출한 코드가 운이 좋아서 통과했지만 사실 이렇게 풀면안된다.

 

찾아보니깐 이미 공식(?)이 있었다. 14세기에 인도의 수학자 나라야나 판디타가 고안했다는데 참 대단하다...

 

arr[5] = [4,2,1,3,5]의 다음 순열을 구해보자. 다음 과정을 그냥 코드로 옮기면 된다.

 

1. arr[k] < arr[k+1]을 만족하는 가장 큰 k를 구한다.

2. k 다음 위치부터 arr[k] < arr[i]를 만족하는 가장 큰 i를 구한다.

3. arr[k]와 arr[i]를 바꾼다.

4. k 다음 위치부터, arr[k+1] ~ arr[end]의 값들을 뒤집는다(좌우반전)

 

※ 1,2 과정에서 가장 큰 index를 구해야 하기 때문에 앞부터 시작하면 좀 번거롭다. 그렇기 때문에 뒤에서 부터 시작한다.

#include <iostream>
#include <vector>

using namespace std;

int main()
{

    int n;
    cin >> n;
    vector<int> v(n);

    for (int i = 0; i < n; i++)
    {
        cin >> v[i];
    }

    int index1 = n - 1;

    while (index1 > 0 && v[index1] < v[index1 - 1])
    {
        index1--;
    }

    if (index1 == 0)
    {
        cout << -1;
        return 0;
    }

    int index2 = n - 1;

    while (v[index1 - 1] > v[index2])
    {
        index2--;
    }

    swap(v[index1 - 1], v[index2]);
    index2 = n - 1;

    while (index1 < index2)
    {
        swap(v[index1], v[index2]);
        index1++;
        index2--;
    }

    for (int i = 0; i < n; i++)
    {
        cout << v[i] << " ";
    }

    return 0;
}