백준 1722 순열의 순서 (C++)

1722번: 순열의 순서

팩토리얼을 이용하여 구현을 하는 문제이다. 이 문제는 두가지 경우로 나뉘는데 해당 순서에 맞는 배열을 출력하는 것과 해당 배열의 순서를 출력하는 두가지이다. 두가지 경우 모두 팩토리얼을 이용해 순서를 구해야한다. 첫번째 경우 주어진 순서 k에 해당하는 배열을 구하기 위해 반복문을 돌며 팩토리얼과 비교해 해당 값을 찾아주었다. 만약 N개의 숫자로 이루어진 배열이 있을 때 첫번째 숫자가 1인 경우의 수는 (N-1)!가지 이다. 두번째 숫자의 경우에는 (N-1-1)!이 된다. 즉 순서 k와 팩토리얼을 비교하여 k가 더 작을 경우를 찾아 해당 값을 저장하고 이를 반복한 후 출력해주었다. 두번째 경우 주어진 배열을 반복문을 돌면서 팩토리얼의 합을 구해 이를 출력해주었다.
생각보다 어려웠던 문제였다. 처음에는 단순히 완전 탐색으로 모든 경우의 수를 구해 주어진 값과 비교하여 출력해주면 된다고 생각했는데 이렇게 되면 값이 너무 커져 시간 초과가 발생했었다. 다른 사람들의 아이디어를 참고해 팩토리얼을 이용하는 방식에 대해 알게 되어 다음과 같이 코드를 바꾸어 통과할 수 있었다. 이러한 방식에 대해 알아두어야 겠다.

#include <iostream>
#include <vector>

using namespace std;

int N, command;
vector<long long> v;
bool check[21];
long long fac[21];

void command1() {
    long long k = v[0];
    vector<int> result;

    for (int i = 0; i < N; i++) {
        for (int j = 1; j <= N; j++) {
            if (check[j]) continue;

            if (k > fac[N - i - 1]) {
                k -= fac[N - i - 1];
            }
            else {
                result.push_back(j);
                check[j] = true;
                break;
            }
        }
    }

    for (int i = 0; i < result.size(); i++) {
        cout << result[i] << " ";
    }
}

void command2() {
    long long result = 0;

    for (int i = 0; i < N; i++) {
        for (int j = 1; j < v[i]; j++) {
            if (check[j]) continue;

            result += fac[N - i - 1];
        }
        check[v[i]] = true;
    }

    cout << result + 1;
}

void solution() {
    fac[0] = 1;
    for (int i = 1; i <= 20; i++) {
        fac[i] = fac[i - 1] * i;
    }

    if (command == 1) command1();
    else command2();
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);

    cin >> N;
    cin >> command;

    long long a;
    if (command == 1) {
        cin >> a;
        v.push_back(a);
    }
    else {
        for (int i = 0; i < N; i++) {
            cin >> a;
            v.push_back(a);
        }
    }

    solution();

    return 0;
}