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

 

 

 

다음 순열을 구하는 문제이다. 처음에는 백트래킹, dfs, 재귀 를 전부 사용해 모든 순열을 찾아가다가 조건에 맞으면 출력하는 방식을 선택하려고 했는데, 범위가 10000 까지이므로 시간 초과가 났다.

 

 

<시간 초과가 난 코드>

 

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

using namespace std;

int N;

vector<int> v;
vector<int> input_v;

bool visited[100001] = {false};


bool same = false;

void dfs(int input)
{
    if(input == N)
    {
        if(same)
        {
            for(auto i : v)
            {
                cout << i << " ";
            }
            same = false;
            return;
        }

        if(v == input_v)
        {
            same = true;

        }

        return;
    }
    else
    {
        for(int i = 0 ; i < N ; i++)
        {
            if(!visited[i])
            {
                visited[i] = true;
                v.push_back(i+1);

                dfs(input + 1);

                v.pop_back();
                visited[i] = false;


            }

        }

    }


}


int main() {

    cin >> N;

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

    bool issame = false;

    for(int i = 0 ; i < input_v.size(); i++)
    {
        if(i+1 == input_v[N-1-i])
        {
            issame = true;
        }
        else issame = false;
    }

    if(issame)
    {
        cout << "-1";
        return 0;
    }

    dfs(0);







    return 0;
}

 

 

다시 살펴보니 시간 초과가 날 수 밖에 없어 보였다.

시간복잡도 문제를 어떻게 해결할 지 생각해보았는데 검색 중

 

C++ stl 함수인 next_permutation() 함수가 있다는 것을 알게 되었다.

자바나 파이썬에는 없다는데, 이런 것까지 있어? 싶어서 내심 놀라웠다.

 

 

next permuation 구현에 대한 내용은 아래 블로그를 참고했다.

간단히 말하자면 가장 긴 감소 부분수열을 찾아 스왑하며 다음 순열을 찾는 것이다.

시간 복잡도가 최대 N으로 평균적으로는 1 정도 걸리는 듯 하다.

 

https://foxtrotin.tistory.com/387

순열 next_permutation()과 prev_permutation() 직접 구현하기

 

 

 

<정답 코드>

 

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

using namespace std;

int N;
vector<int> input_v;

void solve() {
    // 현재 벡터가 마지막 순열이면 -1 출력
    if (!next_permutation(input_v.begin(), input_v.end())) {
        cout << "-1";
        return;
    }
    // 다음 순열 출력
    for (int i : input_v) {
        cout << i << " ";
    }
}

int main() {
    cin >> N;

    input_v.resize(N);
    for (int i = 0; i < N; i++) {
        cin >> input_v[i];
    }

    solve();
    return 0;
}