10972번

10972번 - 다음 순열

이 문제는 오름 차순과 내림차순을 잘 이용해야 풀 수 있었다.

일단 사전순으로 정렬된 가장 작은 순서는 오름차순이 된다. 그리고 순열의 가장 마지막 번호는 내림 차순이 된다. 

예를 들어 1 2 3 4 는 가장 첫수는 오름차순으로 정렬된 상태이고 마지막 수 4 3 2 1 은 내림차순으로 정렬된 상태이다.

그리고 이 다음 순열은 1 2 4 3 이 된다. 이때, 오름차순이었던 수에서 내림차순이 발생한다. 

즉 나는 다음순열을 구할 때의 핵심은 오름 차순은 정렬 할 구간, 내림차순은 앞으로 정렬 된 구간이라고 생각하고 풀었다.

 7 2 4 6 5 3 1 이라는 순열이 있다고 해보면, 

7 2 내림차순, 2 4 6 오름차순, 6 5 3 1 내림차순이 된다. 따라서 오름차순은 정리를 해야하기 때문에, 오름차순의 가장 끝 수를 먼저 찾는다.

이때 변곡점을 제외하면 가장 끝 수는 4가 된다. 이 때 index 값을 2라고 하면 increase = 2가 된다.

그렇다면 이제 주어진 수에서 increase 값보다 큰 값 중에서 제일 작은 값을 increase 보다 큰 내림차순에서 구해서 바꿔주면 된다.

그러고 내림차순을 다시 오름차순으로 바꿔주면 된다. (나는 이 과정에서 swap 을 이용했다.)

 

<정답 코드>

#include<iostream>
#include<vector>
using namespace std;
void next(vector<int> &v)
{
    int increase = -1;
    int decrease;
 
    //변곡점이 아닌 오름차순의 끝 구하기
    for (int i = 0; i < v.size() - 1; i++)
    {
        if (v[i] < v[i + 1])
        {
            increase = i;
        }
    }
    
    //오름차순의 끝을 구할 수 없을 때
    if (increase == -1)
    {
        cout << "-1" << endl;
        return;
    }
 
    //변곡점을 포함한 내림차순 중에서 오름차순 끝보다 큰 값 구하기
    for (int i = increase + 1; i < v.size(); i++)
    {
        if (v[increase] < v[i])
        {
            decrease = i;
        }
    }
    //두점 교환
    swap(v[increase], v[decrease]);
 
    //increase 다음 점들은 다시 오름차순으로 만들기(원래 내림차순이었으므로 뒤집으면 된다)
    int last = v.size() - 1;
    while (increase + 1 < last)
    {
        swap(v[increase+1], v[last]);
        increase++;
        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];
    }
 
    next(v);
 
    return 0;
}