1722 순열의 순서

문제 링크

내 풀이

#include <bits/stdc++.h>

using namespace std;

long long N, k, n[20], fac[21];
int c;

int main(void) {
    list<int> nums;
    cin >> N;
    nums.push_back(1);
    fac[1] = 1, fac[0] = 1;

    for (long long i = 2; i <= N; i++) {
        fac[i] = fac[i-1] * i;
        nums.push_back(i);
    }

    cin >> c;
    if (c == 1) {
        cin >> k;
        int idx = 0;
        int t = N - 1;
        while (!nums.empty()) {
            list<int>::iterator p = nums.begin();
            for (int i = 1; i <= N; i++) {
                if (k <= fac[t] * i) {
                    n[idx] = *p;
                    nums.remove(*p);
                    idx++;
                    if (k > (fac[t] * ((long long)i - 1)))
                        k -= fac[t] * ((long long)i - 1);
                    t--;
                    break;
                }
                p++;
            }
        }
        for (int i = 0; i < N; i++)
            cout << n[i] << " ";
        cout << "\n";
    }
    else {
        int t;
        long long ans = 1, idx;
        for (int i = 1; i <= N; i++) {
            idx = 0;
            cin >> t;
            for (auto j = nums.begin(); j != nums.end(); j++) {
                if (*j == t)
                    break;
                idx++;
            }
            nums.remove(t);
            ans += fac[N - i] * idx;
        }
        cout << ans << "\n";
    }
    return 0;
}