[알고리즘 문제] 백준1722 - 순열의 순서

https://www.acmicpc.net/problem/1722

1722번: 순열의 순서

이 문제는 k번째 수열을 구하는 문제와 수열이 주어졌을 때 해당 수열이 몇번째이냐? 를 묻는 2개의 문제입니다.

그 중 첫번째 문제는 https://kosaf04pyh.tistory.com/192?category=1042517와 같은데 좀 다른 방법으로 문제를 해결하고 있습니다.

 

1. 1~n 범위의 수열이 있고 n과 k가 주어졌을 때 k번째 수열을 구하는 문제 입니다.

예를 들어 n이 4이고 k가 8인 경우를 생각해 봅시다. 첫번째 수열은 [1,2,3,4]입니다. 그렇다면 앞자리가 1인 수열은 모두 몇개 일까요 ?

 

1 2 3 4 

1 2 4 3 

1 3 2 4 

1 3 4 2 

1 4 2 3 

1 4 3 2 

 

총 6가지의 경우의 수가 나옵니다. 이를 다시 생각해보면 6이라는 숫자는 제일 앞자리는 1로 고정되고 나머지 [2,3,4]를 나열할 수 있는 가지의 수 입니다. 3!가 되는거죠. 이는 마찬가지로 제일 앞자리가 2,3,4인 경우도 모두 3! 경우의 수를 가집니다. 

 

그렇다면 다시 k가 3!보다 크다는 것은 무엇을 의미할까요 ?

3!은 1이 제일 앞자린 수열의 경우의 수를 의미했기 때문에 k > 3!이라는 것은 일단 앞자리가 1보다 크다는 것을 의미합니다. 한마디로 앞의 자리가 2,3,4중 하나라는 것이죠. 

 

반대로 k가 3!보다 작다는 것은 무엇을 의미할까요 ?

1이 제일 앞에우는 경우가 3!이기 때문에 k < 3!이라는 말은 앞자리가 1이라는 의미겠죠. 이로써 k번째 수열의 하나가 결정되었습니다. 이때 1은 사용했기 때문에 check[]라는 배열에 체크를 해줍니다. 여기서 k가 3!보다 작을 때, 하나의 숫자가 결정되었습니다. 이는 위에서 만약 k > 3!인 경우 k값에서 3!을 빼주어여 합니다. 

 

 

 

 

2. 수열이 주어졌을 때, 해당 수열이 몇번째 수열인지는 구하는 문제 입니다.

예를 들어 2 4 3 1이 몇번째 수열인지 구하는 경우를 생각해 봅시다. 

---

 

1 2 3 4 1

1 2 4 3 2

1 3 2 4 3 

1 3 4 2 4

1 4 2 3 5

1 4 3 2 6

 

2 1 3 4 7

2 1 4 3 8

2 3 1 4 9

2 3 4 1 10

2 4 1 3 11

2 4 3 1 12

---

1 ? ? ? : 3!                           > 천의 자리 k는 k < 2인 숫자

2 1 ? ? : 2! , 2 3 ? ? : 2!       > 백의 자리 k는 2를 포함하지 않으면서 k < 4인 숫자

2 4 1 ? : 1!                           > 십의 자린 k는 2,4를 포함하지 않으면서 k < 3인 숫자

 

3! + 2! + 2! + 1! + 1(2,4,3,1인 경우) => 12가 됩니다.

#include <iostream>
#include <vector>

using namespace std;

bool check[21];
long long fac[21];

int main()
{

    int N;
    cin >> N;

    int cmd;
    cin >> cmd;

    fac[0] = 1;

    for (int i = 1; i < 21; i++)
    {
        fac[i] = i * fac[i - 1];
    }

    if (cmd == 1)
    {

        long long k;
        cin >> k;

        vector<int> vec(N);

        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
                {
                    vec[i] = j;
                    check[j] = true;
                    break;
                }
            }
        }

        for (int i = 0; i < N; i++)
        {
            cout << vec[i] << " ";
        }
    }
    else
    {
        vector<int> vec(N);
        for (int i = 0; i < N; i++)
        {
            cin >> vec[i];
        }

        long long result = 0;

        for (int i = 0; i < N; i++)
        {
            for (int j = 1; j < vec[i]; j++)
            {
                if (check[j])
                {
                    continue;
                }
                result += fac[N - 1 - i];
            }
            check[vec[i]] = true;
        }

        cout << result + 1;
    }
    return 0;
}