[백준][C++] 10972 - 다음 순열 (next_permutation)

📌문제 설명

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

 

💡생각

1. DFS를 이용해서 순열을 계속 구한다.
2. 입력받은 순열과 같은 순열을 만난다면 값을 true로 바꾼다.
3. 이후 나오는 순열을 출력한다.

#include <iostream>
#include <vector>
#include <algorithm>
#include <stack>
using namespace std;

vector<int> v;
vector<int> save;
bool flag = false;
bool answer = false;
bool isAnswer(){
    if(v == save){
        return true;
    }
    return false;
}
void dfs(bool * visited, int N){
    if(v.size() == N){
        if(!flag){
            if(isAnswer()){
                flag = true;
            }
        }else{
            for(int a : v){
                cout << a << " ";
            }
            answer = true;
            return;
        }
    }
    else{
        for(int i = 1; i <= N; i++){
            if(answer) return;
            if(!visited[i])
            {
                visited[i] = true;
                v.push_back(i);
                dfs(visited, N);
                visited[i] = false;
                v.pop_back();
            }
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int N;
    int temp = 0;
    cin >> N;
    bool visited[N + 1];
    for(int i = 1; i <= N; i++){
        visited[i] = false;
    }
    for(int i = 1; i <= N; i++){
        cin >> temp;
        save.push_back(temp);
    }
    dfs(visited, N);
    if(!answer){
        cout << -1;
    }
}

재귀로 구현을 하니까 시간초과가 바로 발생해버렸다.

비교하는 과정이 너무 많아서 그럴 수 있을 거 같다. 그리고 정답을 출력한 이후에도 실행된 모든 재귀함수를 종료하기 위해서 return을 반복하기 때문에 시간 초과가 발생한 거 같다.

🔥풀이

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

using namespace std;


int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int N;
    cin >> N;
    vector<int> v(N);
    for(int i = 0; i < N; i++){
        cin >> v[i];
    }

    if(next_permutation(v.begin(), v.end())){
        for(int i : v) cout << i << " ";
    }else{
        cout << -1;
    }
    return 0;
}

next_permutation이라는게 존재하는지 처음 알았다..

 

next_permutation

• 다음 순열이 존재한다면 true
• 다음 순열이 존재하지 않다면 false
• 정렬된 상태일 때 모든 순열을 탐색하는게 가능하다.

📕참고