[프로그래머스][Level2] 줄 서는 방법 c++

https://programmers.co.kr/learn/courses/30/lessons/12936 

프로그래머스

 

풀이 과정

이 문제는 next_permutation 알고리즘으로 풀면 쉽게 풀리지만,  그렇게 해선 시간초과가 나는 문제이다.
해결 방법은 팩토리얼을 사용하여 각 자리의 수를 직접 구해야 된다.

 

풀이 1

#include <string>
#include <vector>

using namespace std;

long long facto(int n){
    if(n == 1) return 1;
    return n * facto(n - 1);
}

void recur(vector<int>& v, long long& k, vector<int>& answer){
    if(v.size() == 1){
        answer.push_back(v[0]);
        return;
    }
    long long f = facto(v.size() - 1);
    for(int i = 1; i <= v.size(); i++){
        if(i * f >= k){
            answer.push_back(v[i - 1]);
            v.erase(v.begin() + i - 1);
            k = k - (i - 1) * f;
            recur(v, k, answer);
        }
    }
}

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

    vector<int> v;
    for(int i = 1; i <= n; i++){
        v.push_back(i);
    }
    recur(v, k, answer);
    return answer;
}

 

풀이 2 - (next_permutation) 효율성 시간초과

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

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

    vector<int> v;
    for(int i = 1; i <= n; i++){
        v.push_back(i);
    }
    int cnt = 0;
    do{
        cnt++;
        if(cnt == k){
            for(int i = 0; i < n; i++){
                answer.push_back(v[i]);
            }
        }
    }while(next_permutation(v.begin(), v.end()));
    return answer;
}