[알고리즘 문제] 백준10793 - 이전 순열

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

10973번: 이전 순열

10972문제와 비슷합니다. 10972문제에서는 다음 순열을 구했지만, 10973문제는 이전 순열을 구하는 문제 입니다.

 

앞에 다음 순열을 구하는 문제에서의 로직은 다음과 같습니다.

 

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번 과정에서 부등호를 수정해주면 되는데,

arr[k] < arr[k+1]을 arr[k] > arr[k+1]로 수정해주면 됩니다. 이는 2번도 마찬가지입니다.

 

 

#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;
}