백준 10974: 모든 순열

지금 내가 강의에서 배우고 있는 부분은 브루트포스로 한마디로 무식하게 경우의 수를 모두 시도해보는 것이다. 그 중 하나인 순열인데 

아래와 같이 STL의 기능을 이용하면 코드를 세련되게 작성할 수 있으나 시간복잡도가 어마무시하다. 순열의 N!의 경우의 수가 있고 N개의 수로 이루어져 있으니 그 시간복잡도는 O(N!* N) 이다. 많은 시간이 소요되다 보니 endl 보다는 개행문자를 아스키코드로 사용했다. 문제 조건인 8만큼은 그래도 주어진 시간안에 해결할 수 있다.

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
 
int main()
{
    int input;
    cin >> input;
    vector<int> perm;
    for (int i = 1; i <= input; ++i)
        perm.push_back(i);
    do
    {
        for (auto itr = perm.begin(); itr != perm.end(); ++itr)
        {
            cout << *itr << " ";
        }
        cout << '\n';
    } while (next_permutation(perm.begin(), perm.end()));
 
    return 0;
}