[백준/c++] 10972번: 다음 순열

 

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

10972번: 다음 순열

 

이 문제는,, 백트래킹을 하면 시간 초과 발생한다.

그래서 고민 좀 하다가 다른 사람이 푼 방법을 봤는데 도저히 내가 생각해낼..ㅋㅋ 게 아니었다ㅠ

그래서 이번 문제를 통해 공부를 하고 다른 문제에 응용할 수 있도록 해야겠다.

 

다음 순열을 찾는 건 사전 순의 정렬 원리를 그대로 구현해야 한다.

예를 들어, 1 2 5 4 3 의 다음 순열은? 뒤에서부터 바꿔나가야 한다. 

→ 뒤에서부터 이어진 증가 순열의 끝을 찾아야 한다. 

맨 뒤(n-1)에서부터 앞으로 나가면서 증가되지 않은 부분을 찾으면 된다.

 

1 2 5 4 3 의 경우, [2, 5] 부분에서 증가되지 않는다. 이 수와 맨 뒤의 수를 swap

그 후, 증가되지 않았던 그 부분(2) 뒤의 순열들을 또 정렬시켜주면 된다.

 

bool next_permutation(){
    //(1)
    int i = n-1;
    while(i>0 && arr[i-1] > arr[i]) --i;
    if(i<=0) return false;                   
    
    //(2)
    int j = n-1;
    while(arr[i-1] > arr[j]) --j;
    swap(arr[i-1], arr[j]);                  

    //(3)
    for(int k=i, h=n-1; k<h; ++k, --h) swap(arr[k], arr[h]);
    
    return true;
}

 

(1) i는 맨 뒤 원소다. 여기서 앞으로 이동하면서 증가되는 부분을 찾는다. 그 부분이 i

1 2 5 4 3 의 경우 arr [i]=3에서 감소되면서 arr [i]=5로 끝난다.

이때, i=0가 되는 경우는 순열 전체가 내림차순이기 때문에 바로 빠져나가 준다. -1 출력

 

(2) j는 맨 뒤 원소다. (1)에서 구한 i의 위치보다 바로 앞과 맨 뒤 원소를 바꿔준다.

1 2 5 4 3 의 경우 arr [i-1] = 2와 arr [n-1] = 3 swap

 

(3) 이제 i-1 아래의 원소들을 오름차순으로 변경해주면 된다.

어차피 i-1부터 n-1까지의 값은 내림차순으로 되어있기 때문에 중앙을 제외하고 앞 뒤 원소들을 swap 하면 된다.

 

내림차순의 구간을 찾아서 오름차순으로 바꿔주는 것이 핵심인 것 같다.

 

#include <iostream>
#include <algorithm>
#include <string>
#define MAX 10000
using namespace std;
int arr[MAX], n;

bool next_permutation(){
    int i = n-1;
    while(i>0 && arr[i-1] > arr[i]) --i;
    if(i<=0) return false;                  //내림차순인 경우: 마지막 순열
    
    int j = n-1;
    while(arr[i-1] > arr[j]) --j;
    swap(arr[i-1], arr[j]);
    
    for(int k=i, h=n-1; k<h; ++k, --h) swap(arr[k], arr[h]);
    
    return true;
}

int main(){
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> n;
    for(int i=0; i<n; i++) cin >> arr[i];
    
    //다음 순열이 존재하는가? - 출력
    if(next_permutation()){
        for(int i=0; i<n; i++) cout << arr[i] << ' ';
        cout << '\n';
    }else{
        cout << "-1\n";
    }
    return 0;
}

 

---

 

 

그런데,, next_permutation()함수를 사용할 수도 있다..!!

#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#define MAX 10000
using namespace std;
int arr[MAX], n;
vector<int> v;

int main(){
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    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] << ' ';
        cout << '\n';
    }else{
        cout << "-1\n";
    }
    return 0;
}