[C++] 백준 10972번 - 다음 순열

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

10972번: 다음 순열

 

 

 

문제

1부터 N까지의 수로 이루어진 순열이 있다. 이때, 사전순으로 다음에 오는 순열을 구하는 프로그램을 작성하시오.

사전 순으로 가장 앞서는 순열은 오름차순으로 이루어진 순열이고, 가장 마지막에 오는 순열은 내림차순으로 이루어진 순열이다.

N = 3인 경우에 사전순으로 순열을 나열하면 다음과 같다.

• 1, 2, 3
• 1, 3, 2
• 2, 1, 3
• 2, 3, 1
• 3, 1, 2
• 3, 2, 1

입력

첫째 줄에 N(1 ≤ N ≤ 10,000)이 주어진다. 둘째 줄에 순열이 주어진다.

출력

첫째 줄에 입력으로 주어진 순열의 다음에 오는 순열을 출력한다. 만약, 사전순으로 마지막에 오는 순열인 경우에는 -1을 출력한다.

 

 

 

 

접근 방법 1)

1~N 의 숫자로 이루어진 순열을 dfs로 구하는데, 차근차근 구해나가면서 입력한 순열과 일치할 때를 찾는다. 

찾으면 flag = true 로 바꾼 뒤, 다음 턴에서 다음 차례의 순열을 출력하고 stop = true로 바꿔서 탐색을 멈춘다.

그러나 이 방법으로는 시간 초과가 떴다. STL을 이용해보자.

 

#include <iostream>
#include <vector>

using namespace std;

int N;
vector<int> vec;
vector<int> ans;
vector<int> greaterVec;
int visited[10000] = {0};

bool flag = false;
bool stop = false;

bool lastChk(){
    
    int n = N;
    bool ret = false;
    for(int i = 0; i<N; i++){
        if(vec[i] == n) {
            ret = true;
            n--;
        }
        else {
            ret = false;
            break;
        }
    }
    return ret;
    
    
}



void search(int toPick){
    
   

    if(toPick==0){
        
        if(flag){
            for(int i = 0; i<ans.size(); i++){
                cout << ans[i] << " ";
            }
            cout << "\n";
            stop = true;
            return;
        }
        int cnt=0;
        for(int i = 0; i<ans.size(); i++){
            if(ans[i]==vec[i]) cnt++;
            else break;
        }
        
        if(cnt==N) {
            flag = true;
           // return;
        }
    }
    
    
    for(int i = 0; i<greaterVec.size(); i++){
        
        if(visited[i] == 0){
            visited[i] = 1;
            ans.push_back(greaterVec[i]);
            search(toPick-1);
            ans.pop_back();
            visited[i] = 0;
            if(stop) {return;}
        }
    }
    
}

int main(){
    
    cin >> N;
    
    int num;
    for(int i = 0; i<N; i++){
        cin >> num;
        vec.push_back(num);
        greaterVec.push_back(i+1);
    }
    
    
    
    if(lastChk()) {
        cout << -1;
    }
    else{
        search(N);
    }
    
    return 0;
}

 

 

 

접근 방법 2)

next_permutation 함수를 이용했다. 이 함수는 vec의 원소 순서 자체를 바꿔버리며 마지막 순열 다음에는 false를 리턴한다. 이 경우는 문제의 요구 조건에 맞게 -1을 출력해주면 된다. 위의 방법보다 매우 간단하게 해결할 수 있는 방법이다. 

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int N;
vector<int> vec;

int main(){


    cin >> N;
    int num;
    for(int i = 0; i<N; i++){
        cin >> num;
        vec.push_back(num);
    }


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

   

    return 0;
}