[C++] 10972 다음 순열

10972번: 다음 순열

 

[ 풀이 규칙 ] 

배열의 뒤에서부터 arr[i]와 arr[i+1]을 비교한다.arr[i]<arr[i+1]인 경우 arr[i] 이후에 있는 값 중 arr[i] 다음으로 큰 수를 arr[i]에 넣고, 그 뒤 배열은 오름차순 정렬시킨 후 출력하면 되는 아주 간단한 문제이다. 

#include <iostream>
#include <algorithm>
#define MAX 10001
using namespace std;

int N;
int arr[MAX] = {0,};

bool solve()
{
    for(int i=N-1; i>=1; i--){
        if(!(arr[i]>arr[i+1])){ //arr[i]<arr[i+1]인 경우 
            int max = 10000;
            int maxIdx = -1;
            for(int j=i+1; j<=N; j++){
                if(arr[j]>arr[i] && arr[j]<max){
                	//i 이후에 있는 값 중 그 다음으로 큰 값과 idx를 찾는다.
                    max = arr[j];
                    maxIdx = j;
                }
            }
            //두 값을 교환한다.
            int tmp = arr[i];
            arr[i] = max;
            arr[maxIdx] = tmp;
            //그 뒤 배열을 정렬한다. 
            sort(arr+(i+1),arr+N+1);
            return false;
        }
    }
    return true;
}

int main() {
    cin>>N;
    
    for(int i=1; i<=N; i++){
        cin>>arr[i];
    }

    if(solve()){ //마지막 순열일 경우 -1을 출력한다. 
        cout<<-1;
    }else{
        for(int i=1; i<=N; i++){
            cout<<arr[i]<<' ';
        }
    }
}