개발 블로그

문제 링크 : www.acmicpc.net/problem/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;
}