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

문제 링크 - https://www.acmicpc.net/problem/10973

🌱 문제

🌱 풀이 1

• prev_permutation 함수 이용
• 알고리즘 헤더 파일 선언
• 첫번째 인자 : 구하고자 하는 순열의 시작, 두번째 인자 : 구하고자 하는 순열의 끝
  ex) bool check = prev_permutation(v.begin(), v.end())
• 함수를 사용 시, 순열의 다음 순열이 존재하면 다음 순열로 바뀌고 true를 반환, 다음 순열이 없으면 그 다음수열(처음시작수열)로 바뀌고 false를 반환.
  ex) 수열이 4321 이면 -> 4312,
  수열이 1234 이면 -> 4321 (한바퀴 돌아서)

🌱 코드 1

//10972번 : 다음순열
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

vector<int> v;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    int n;
    cin>>n;
    for(int i=0; i<n; i++){
        int x;
        cin>>x; 
        v.push_back(x);
    }

    if(next_permutation(v.begin(),v.end())){
    for(int i=0; i<n; i++){
        cout<<v[i]<<" ";
     }
    }
    else{for(int i=0; i<n; i++){
        cout<<v[i]<<" ";
     }
        cout<<-1<<"\n";
    }

}

🌱 풀이 2

• 주어진 수열이 어느 인덱스를 기점으로 마지막 수열인지 찾는다.
  ex) 수열이 25468이면, 다음수열은 24865 이므로, 25468은 1번째 index인(index 0부터 시작) 4를 기점으로 마지막 수열이다. -> 이때의 index를 i 라 하자.
• 25468 에서
  24865 로 넘어가는 과정을 보면
  5(i-1 index)가 다음 숫자인 4 (이전수열 기준)으로 바뀌고, 그 뒤에는 인덱스 상관없이 가장 큰수가 온다.(즉, 내림차순! -> 865)
• 정리하면 i-1번 수가 어떤수로 변경되는지 찾아야 하는데, 그 수는 n-1번째 인덱스로부터 가장 가까이 있으면서 i-1번째 수보다 작은 수 이다.
  ex) 25346 에서 3를 기점으로 마지막 수열이고, n-1인덱스로부터 가장 가까우면서 5(i-1)보다 작은 수는 4이므로 5와 4가 서로 바뀌고 나머지 오른쪽에 놓인 숫자들은 거꾸로 배열시켜서 24653가 이전 수열이다.

정리하면

1. 수열에서 어느 인덱스를 기점으로 마지막 수열인지 찾는다 -> i번 index
2. i-1번째 수를 그 다음수로 바꾼다.
   • 그 다음수란 i-1번째보다 가장 멀리있으면서 i-1번 수보다 작은 숫자이다. 그수를 j번째수라하자.
3. i-1번째수와 j번째 수를 바꾼다.
4. i번째 수부터 n-1번 수 까지를 뒤집는다.
   -> 그 이전수열 완성

🌱 코드 2

//10973번 : 이전순열
#include <iostream>
using namespace std;

//1. 수열에서 어느 인덱스를 기점으로 마지막 수열인지 찾는다 -> i
//2. i-1번째 수를 그 다음수로 바꾼다.
//그 다음수란  i-1번째보다 가장 멀리있으면서 i-1번 수보다 작은 숫자이다. 그수를 j번째수라하자.
//3. i-1번째수와 j번째 수를 바꾼다.
//4. i번째수부터 n-1번째수를 뒤집는다.
//그 이전수열 완성


bool func(int arr[], int n){
    int i=n-1;
    while(i>0 && arr[i]>arr[i-1])
    i--;

    if(i<=0)
    return false;

    int j= n-1;
    while(arr[i-1]<arr[j])
    j--;

    swap(arr[i-1],arr[j]);
    j=n-1;
    while(i<j){
        swap(arr[i],arr[j]);
        i++;
        j--;
    }
    return true;


}


int arr[10001];

int main(){
    int n; 
    cin>>n;
    for(int i=0; i<n; i++){
        cin>>arr[i];
    }
    if(func(arr,n)){
        for(int i=0; i<n; i++){
            cout<<arr[i]<<" ";
        }
    }else{
        cout<<-1<<"\n";
    }
    
}