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

 이 문제는 수학 문제에 가깝게 풀었다. 일단 최대 n의 크기가 20인데, 20!은 2,432,902,008,176,640,000 라는 엄청난 수가 나오고, 당연히 단순 순회로는 이 문제를 풀 수 없다. 그러나 한가지 중요한 점은 20!이 long long 자료형에 담긴다는 사실이다. 즉, 팩토리얼을 이용한 어떤 수식을 사용할 수는 있다.

 

 

 일단 n = 4 일때의 모든 순열을 구하고, 규칙을 찾아봤다.

1 2 3 4 - 0
1 2 4 3
1 3 2 4
1 3 4 2
1 4 2 3
1 4 3 2
2 1 3 4 - 6
2 1 4 3
2 3 1 4
2 3 4 1
2 4 1 3
2 4 3 1
3 1 2 4 - 12
3 1 4 2
3 2 1 4
3 2 4 1
3 4 1 2
3 4 2 1
4 1 2 3 - 18
4 1 3 2
4 2 1 3
4 2 3 1
4 3 1 2
4 3 2 1

 순열 옆의 숫자들은 해당 순열이 k번째 (0번부터 시작했을 때) 임을 나타낸다. 여기서 중요한 것은 순열 맨 앞인데, 1 2 3 4 순서대로 당연히 정렬되어 있지만, 그 한 덩어리가 3!개씩 이루어져 있다는 것이다. 즉, 임의의 숫자 k에 대해 (n - 1)! 로 나누면 해당 숫자 k의 첫 번째 숫자에 대한 단서를 얻을 수 있다. 이 점을 이용해서, 1부터 n까지의 배열을 만들고, 해당 인덱스를 계산해낸 뒤 그 숫자를 배열에서 제거하는 방식으로 구현했다.

 

 

 전체 코드는 다음과 같다.

#include <string>
#include <vector>

using namespace std;

long long factorial[21];

vector<int> solution(int n, long long k) {
    vector<int> answer;
    
    // base case
    if (n == 1) {
        answer.push_back(1);
        
        return answer;
    }
    
    factorial[0] = 0;
    
    long long tempFac = 1;
    for (int i = 1; i <= 20; i++) {
        tempFac *= i;
        factorial[i] = tempFac;
    }
    
    k--;
    
    vector<int> temp;
    for (int i = 1; i <= n; i++) {
        temp.push_back(i);
    }
    
    while (temp.size() > 1) {
        int size = temp.size();
        
        int index = k / factorial[size - 1];
        
        answer.push_back(temp[index]);
        temp.erase(temp.begin() + index);
        
        k %= factorial[size - 1];
    }
    
    answer.push_back(temp[0]);
    
    return answer;
}