10973번

10973번 - 이전 순열

10972 번과 같은 방식으로 푼다. 다만 이전 순열이기 때문에 모든 걸 반대로 해줘야한다.

이전 순열의 경우는 내림차순일 경우 정렬할 구간, 오름차순일 경우 정렬된 구간이라고 생각하면 된다.

<정답 코드>

#include<iostream>
#include<vector>
using namespace std;
void prev(vector<int> &v)
{
    int increase = -1;
    int decrease = -1;
 
    //변곡점이 아닌 내림차순의 끝 구하기
    for (int i = 0; i < v.size() - 1; i++)
    {
        if (v[i] > v[i + 1])
        {
            decrease = i;
        }
    }
    
    //내림차순의 끝을 구할 수 없을 때
    if (decrease == -1)
    {
        cout << "-1" << endl;
        return;
    }
 
    for (int i = decrease + 1; i < v.size(); i++)
    {
        if (v[decrease] > v[i])
        {
            increase = i;
        }
    }
    //두점 교환
    swap(v[increase], v[decrease]);
 
    int last = v.size() - 1;
    while (decrease + 1 < last)
    {
        swap(v[decrease+1], v[last]);
        decrease++;
        last--;
    }
 
    for (int i = 0; i < v.size(); i++)
    {
        cout << v[i] << " ";
    }
    cout << endl;
}
int main()
{
    int N;
    vector<int> v;
 
    cin >> N;
 
    v.resize(N);
 
    for (int i = 0; i < N; i++)
    {
        cin >> v[i];
    }
 
    prev(v);
 
    return 0;
}