[프로그래머스 12936] 줄 서는 방법

문제출처

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

소스코드

효율성 - 시간초과

(next_permutation은 모든 순열을 다 보면서 세기때문에 시간복잡도가 O(n!)이다....

#include <string>
#include <vector>
#include <algorithm>
using namespace std;
 
vector<int> solution(int n, long long k) {
    vector<int> answer(n, 0);
    for(int i=0; i<n; i++) answer[i] = i+1;
    for(int i=0; i<k-1; i++) next_permutation(answer.begin(), answer.end());
  
    return answer;
}

정답 코드

#include <vector>
using namespace std;
 
long long makeFactorial(long long n) {
    long long ret=1;
    for(long long i=1; i<=n; i++) ret*=i;
    return ret;
}
 
vector<int> solution(int n, long long k) {
    vector<int> answer;
    vector<int> v(n,0);
    for(int i=0; i<n; i++) v[i] = i+1;
    
    int num=n;
    int quotient;
    long long remain;
    long long fac;
    while(num>0) {
        num--;
        fac=makeFactorial(num);
        remain = k % fac;
        quotient = (int)(k / fac);
        
        if(remain==0) {
            quotient--;
            answer.push_back(v[quotient]);
            v.erase(v.begin()+quotient);
            break;
        }
        
        answer.push_back(v[quotient]);
        v.erase(v.begin()+quotient);
        k=remain;
    }
    
    for(int i=v.size()-1; i>=0; i--) {
        answer.push_back(v[i]);
        v.erase(v.begin()+i);
    }
    
    return answer;
}