Level 2. 줄 서는 방법

Level 2. 줄 서는 방법

 

 

next_permutation() 함수로 간단하게 해결하면 시간 초과가 발생한다.

 

// 이 풀이는 시간 초과가 발생한다.
#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>

using namespace std;

vector<int> solution(int n, long long k)
{
    vector<int> answer(n);

    iota(answer.begin(), answer.end(), 1);

    while (--k)
        next_permutation(answer.begin(), answer.end());

    return answer;
}

 

#include <iostream>
#include <vector>
#include <numeric>

using namespace std;

long long factorial(int n)
{
    return (n <= 1) ? 1 : n * factorial(n - 1);
}

vector<int> solution(int n, long long k)
{
    vector<int> answer;
    vector<int> numbers(n);

    iota(numbers.begin(), numbers.end(), 1);

    while (0 < n)
    {
        long long fac = factorial(n) / n;
        int idx = (k - 1) / fac;
        idx = (idx < 0) ? 0 : idx;

        k %= fac;
        k = (k) ? k : fac;

        answer.emplace_back(numbers[idx]);
        numbers.erase(numbers.begin() + idx);

        --n;
    }

    return answer;
}