줄 서는 방법 - level 3

해결방법

쉬운듯 어려운 문제였다. 해결방법은 머리 속으로 바로 생각났는데 처음 구현해보는 알고리즘이라 고생을 많이 했다. 충분히 프로그래머스를 이용하여 코딩테스트를 보는 회사에서 나올 수 있는 문제라고 여겨진다.
k번째의 경우의 수를 구하는 문제이다. 만약 아래와 같이 next_permutation으로 푼다면 효율성 테스트를 통과하지 못해 효율적인 방법을 생각해내야 한다.

 do {
     k--;
    if(k == 0) break;
 } while(next_permutation(answer.begin(), answer.end()));

factorial을 이용하여 문제를 푼다면 더 빠르게 풀 수 있다. 예를 들어 보자! n = 10이라고 가정한다. 만약 첫 번째 자리수가 바뀌기 위해서는 k > 9! 하므로, k < 9!일 경우 배열의 첫 번째는 1임을 알 수 있다. 따라서 k / factorial(n - 1) = n번째의 수라고 할 수 있다.
$$ index = \lfloor{k / factorial(n-1)}\rfloor $$
만약 index값이 0이라면 n번째 수는 변하지 않는다. 만약 0보다 큰 값이 나온다면 그 수가 곧 n번째의 값이 된다.
유의할 점은 문제 설명은 1 ~ n!까지의 경우의 수를 염두해 두었지만, 프로그래밍 언어는 인덱스가 0부터 시작한다는 점을 유의해야 한다. 시작 전에 k를 -1해주고 시작하여야 한다.

소스코드

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