백준 10973번 이전 순열 (C++)

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

10973번: 이전 순열

next_permutation만 알고 있었는데, 이 문제를 풀면서 prev_permutation을 알게되었다.

perv_permutation의 뜻은 말 그대로 next_permutation의 반대, 즉, 오름차순이 아닌 내림차순으로 출력이 된다.

 

문제 풀이는 다음과 같다. 

1. 목표값을 배열을 입력받고 perv_permutation을 사용하기 위해 동일한 배열을 하나 더 만든다.

2. 복사된 배열로 prev_permutation을 실행한다.

단, 이때 prev_permutation을 사용하기 이전에 오름차순/내림차순으로 정렬할 필요가 없다.

목표값의 첫 번째 자리에 있는 숫자부터 prev_permutation을 사용해야지 시간초과가 안나오기 때문이다.

3. prev_permutation을 통해 목표값의 배열이 나오면 조건 1 bool문을 true로 바꿔준다. 

4. 다음 순열을 진행하고, 이때 조건 1이 true라면 순열 값들을 출력해준다.

출력을 무사히 진행했으니 조건2 bool문을 true로 바꿔준다. 

조건2를 설정한 이유는, 만약 목표한 배열의 값과 동일한 순열이 나와서 조건1이 true가 됐지만, 해당 순열이 마지막 차례의 순열이라 다음 값이 존재하지 않는다면 -1을 출력해야하기 때문이다.

5. 만약 조건2가 false라면 최초 입력값의 내림차순 순열이 없다는 의미이다. 때문에 -1을 출력한다.

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

int arr[MAX], v[MAX];

int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    int n = 0;
    bool ch = false, done = false;
    cin >> n;
    for(int i=0; i<n; i++) {
        cin >> arr[i]; // 찾아야하는 원본
        v[i] = arr[i];
    }
    do{
        if(ch){
            for(int i=0; i<n; i++){
                cout << v[i] << " ";
            }
            done = true;
            break;
        }
        for(int i=0; i<n; i++){
            if(v[i]==arr[i]) ch = true;
            else{
                ch = false;
                break;
            }
        }
    }while(prev_permutation(v,v+n));
    if(!done) cout << -1 << "\n";
    return 0;
}