백준 알고리즘 풀이 10973번 - 이전 순열

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

10973번: 이전 순열

 

---

 

- 순열 문제

 

알고리즘

---

1. 뒤에서부터 n[i] > n[i+1]인 i를 찾아서 index에 저장  

2. 뒤에서부터 index까지 arr[index] > arr[j]인 j를 찾아서, arr[index]와 arr[j]를 바꾸어준다. 

3. index+1부터 수열 끝까지 뒤집어준다.

 

시간 복잡도

---

O(N)

 

소스코드

---

#include <iostream>
using namespace std;

int arr[10001];
int n;
int check = false;
void reverse(int start,int end)
{
    int num = (end-start+1)/2;
    for(int i=0;i<num;i++){
        int temp = arr[start+i];
        arr[start+i] = arr[end-i];
        arr[end-i] = temp;
    }
}

void pre_permu(){
    int index = 0;
    for(int i=n-1;i>=1;i++){
        if(arr[i]>arr[i+1]){
            index = i;
            check = true;
            break;
        }
    }
    for(int j=n;j>index;j++){
        if(arr[index]>arr[j]){
            int temp = arr[index];
            arr[index] = arr[j];
            arr[j] = temp;
            break;
        }
    }
    reverse(index+1,n);
}

int main()
{
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>arr[i];
    }
    pre_permu();
    if(!check){
        cout<<"-1";
    }
    else{
        for(int i=1;i<=n;i++){
            cout<<arr[i];
        }
    }
}

 

 

틀린 내용이나 지적 언제나 환영입니다.

도움이 되었다면 하트 한번씩 눌러주세요:)