프로그래머스 Level3_ 줄 서는 방법 (C++)

처음에 백트래킹 썼다가 시간초과나서 규칙 찾고 하느랴 시간 다버렸다.

팩토리얼을 이용한다.  idx = k / fact [n-i];

위 식을 이용하면 각 위치가 몇번째인지 알 수 있다.

그리고 몇번째인지 안다고해서 다되는것이 아니라 앞에서 나온 수는 거르고 그 다음 것을 선택해야 된다.

이 부분은 계속 시간초과나고 도저히 모르겠어서 다른사람 답을 살짝보고(...) 벡터를 사용했다.

#include <string>	// Level3_ 줄 서는 방법 [수학] [구현]
#include <vector>
#include <algorithm>

#include <iostream>
using namespace std;

long long fact[21] = {1, };
vector<int> solution(int n, long long k) {
    vector<int> answer;
	vector<int> v;
	for(int i=1; i<=n; i++){
		fact[i] = fact[i-1] * i;
		v.push_back(i);
	}
	k-=1;
	for(int i=1; i<=n; i++){
		int idx = k/fact[n-i];
		answer.push_back(v[idx]);
		v.erase(v.begin() + idx);
		k %= fact[n-i];
    }

    return answer;
}

// 입출력
int main(){
	int n;
	long long k;
	cin >> n >> k;

	for(auto i : solution(n, k)){
		cout << i << " ";
	}
}