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

 

문제풀이

 

next_permutation 으로 그냥 돌리고 해당 index에서 반환하는 방식을처음 썼는데

 

시간초과가 났다.

 

효율성 문제였다.

 

순열의 특징을 이용하여 앞자리부터 계산해 나간다. 첫자리가 같은 경우의 가짓수는  (n-1)! 이다.

이개념을 바탕으로 아래에 코드를 작성하였다.

소스코드

#include <string>
#include <vector>
#include <algorithm>
#include <vector>
 
using namespace std;
 
vector<int> people;
 
vector<int> solution(int n, long long k) {
    vector<int> answer;
    long long factorial = 1;
    for(int i=1;i<=n;i++){
        factorial *=i;
        people.push_back(i);
    }
    
    k--;
    
    while(n>0){
        factorial/=n;
        n--;
        answer.push_back(people[k/factorial]);
        people.erase(people.begin() + k/factorial);
        k %= factorial;
    }
    return answer;
}

 

문제 링크 : www.programmers.co.kr/learn/courses/30/lessons/12936

프로그래머스