- factorial을 이용하면 된다.
- [1,2,3,4]를 통해서 순열을 만들 때
- 앞을 [1, x, x, x]처럼 1로 고정을 하면 뒤에서 2-3-4가 순열로 들어가므로 총 3!의 순열이 생길 수 있다.
- 즉, 1로 시작하는 가장 마지막 순열 [1, 4, 3, 2]는 3!의 순서라고 할 수 있다.
- 그러면 만약에 [3, 1, 2, 4]의 경우에는 [1, x, x, x]과 [2, x, x, x] 각각 3!로 12(3! + 3!)번째 다음인 13번째가 된다.
- 만약에 k=13이라면
- 제일 앞에 1을 고정했을 때 3!의 경우를 빼고, 2를 고정했을 때 3!의 경우를 빼고 => 13 - 3! -3! = 1
- 이제 그 다음에 제일 앞에 3이 왔을때의 3!의 1보다 크니까 제일 앞은 3이 되는 순열임을 알 수 가 있다.
- f[21] : factorial을 저장하기 위한 배열
- check[21] : 순열에 1~20까지의 숫자가 들어갔는지 확인하기 위한 배열
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
long long f[21] = {1,}; // -> f[n] : n!
int check[21] = {false,}; // -> 1~20의 수중에서 순열에 할당이 되었는지 확인하는 배열
vector<int> solution(int n, long long k) {
vector<int> answer(n);
// 팩토리얼 구해두기
for(int i=1; i<=20; i++){
f[i] = f[i-1] * i;
}
for(int i=0; i<n; i++){
// 순열의 순서는 1부터 큰 순서대로 순서가 증가하니까
// 1-2-3-4 -> 1-2-4-3
for(int j=1; j<=n; j++){
// 만약 이미 순열에 할당이 되어있는거면 Pass
if(check[j] == true) continue;
// n부터 (i+1)개만큼 뺸 나머지위치들의 순열의 갯수를 구하면
// 예를 들면
// 1-2-X-X-X의 경우라면 i=1이니까
// f[n - (i+1)] = f[5 - (i+1)] = f[5 - (1 + 1)] = f[3] = 6
if(k > f[n - (i+1)]){
k -= f[n - (i+1)];
}
// k <= f[n - (i+1)]
// 앞에다가 숫자를 고정
else{
check[j] = true;
answer[i] = j;
break; // i 위치에 할당을 했으므로 넘어감
}
}
}
return answer;
}
/*next_permutation
vector<int> solution(int n, long long k) {
vector<int> answer;
long long count = 1;
for (int i=1; i<=n; i++){
answer.push_back(i);
}
do{
if(count == k){
break;
}
count++;
}while(next_permutation(answer.begin(), answer.end()));
return answer;
}
*/
- 생각하지 않고 next_permutation()만 믿고 했다...
- 이전에 풀었던 문제였던것만 기억나고 풀이방법은 기억이 나지 않았다. => 복습을 제대로 하자