10974번

10974번 - 모든 순열

모든 순열을 구하는 문제인데, 사전식으로 출력하라고 했으니,

next_permutation 을 쓰면 된다. ( 10972번)

단 시간 초과 문제로 cin,cout 대신 printf 를 사용해야한다.

<정답 코드>

#include<iostream>
#include<vector>
using namespace std;
 
bool next(vector<int> &v)
{
    int inc = -1;
    int dec = -1;
 
    for (int i = 0; i < v.size()-1; i++)
    {
        if (v[i] < v[i + 1])
        {
            inc = i;
        }
    }
 
    if (inc == -1)
    {
        return false;
    }
 
    for (int i = inc + 1; i < v.size(); i++)
    {
        if (v[inc] < v[i])
        {
            dec = i;
        }
    }
 
    swap(v[inc], v[dec]);
 
    int last = v.size() - 1;
    
    while (inc + 1 < last)
    {
        swap(v[inc + 1], v[last]);
        inc++;
        last--;
    }
 
    return true;
}
 
int main()
{
    int N;
    vector<int> v;
 
    cin >> N;
    v.resize(N);
 
    for (int i = 0; i < N; i++)
    {
        v[i] = i + 1;
    }
    
    while (true)
    {
        for (int i = 0; i < N; i++)
        {
            printf("%d ", v[i]);
        }
        printf("\n");
 
        if(!next(v))
        {
            break;
        }
    }
    return 0;
}