[ 백준 / C++ ] 10973 : 이전 순열

[ 문제 ]

 

10973번: 이전 순열

 

[ 접근방법 ]

 

먼저 순열 뒤에서부터 앞으로 탐색하면서 처음으로 연속한 수가 감소하는 인덱스를 찾는다.

= vec[ idx ] > vec[ idx + 1 ]

 

vec[ idx ] 뒤에서 이보다 작으면서 제일 큰 수를 찾는다.

= vec[ idx ] > vec[ midx ], idx < midx 를 만족하는 vec[ midx ] 중 제일 큰 수

 

마지막으로 vec[ idx ] 와 vec[ midx ] 를 교환한 후, vec[ idx ] 뒤를 내림차순 정렬한다.

1 3 2 4 5 → 1 2 3 4 5  → 1 2 5 4 3

 

[ 소스코드 ]

 

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int n;
vector<int> vec;

bool cmp(int x, int y){
    return x > y;
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> n;
    vec.resize(n);
    for(int i = 0; i < n; i++)cin >> vec[i];

    int idx;
    for(idx = n - 2; idx >= 0; idx--){
        if(vec[idx] > vec[idx + 1]){
            break;
        }
    }

    if(idx < 0){
        cout << "-1";
        return 0;
    }

    int midx = idx + 1;
    for(int i = idx + 2; i < n; i++){
        if(vec[midx] < vec[i] && vec[i] < vec[idx]){
            midx = i;
        }
    }

    swap(vec[idx], vec[midx]);

    sort(vec.begin() + idx + 1, vec.end(), cmp);

    for(auto i : vec)cout << i << " ";

    return 0;
}