[백준] 1722번 순열의 순서

문제

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

풀이과정

N이 주어지면 k번째 순열을 출력하거나 순열을 입력받아서 몇 번째 순열인지 출력하는 문제다.

처음에 문제를 보고 next_permutation을 쓰면 쉽게 풀릴 줄 알고 썻는데 너무 쉽게 풀려고 했나보다 N의 최대값이 20이기 때문에 브루트 포스로 풀면 시간초과가 나버린다.

아래와 같은 알고리즘을 통해 구현을 해야 시간초과가 안나고 해결할 수 있다.

입력 순열로 5 2 4 7 6 3 1 이 주어지면
1 ? ? ? ? ? ? - 6!개 , 2 ? ? ? ? ? ? 6!개, 3 ? ? ? ? ? ? 6!개, 4 ? ? ? ? ? ? 6!개
5 1 ? ? ? ? ? - 5!개
5 2 1 ? ? ? ? - 4!개, 5 2 3 ? ? ? ? - 4!개
5 2 4 1 ? ? ? - 3!개, 5 2 4 3 ? ? ? - 3!개, 5 2 4 6 ? ? ? - 3!개
5 2 4 7 1 ? ? - 2!개, 5 2 4 7 3 ? ? - 2!개,
5 2 4 7 6 1 ? - 1!개
이 과정을 모두 더하면 몇 번째 순열인지 확인할 수 있다. 이러한 과정을 반대로 진행하면 k번째 순열을 출력할 수도 있다.

소스코드

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

long long f[21]; // 1!~20! 까지 값을 저장할 변수
bool check[21]; // 1~N까지의 숫자가 순열에 있는지 없는지 확인하는 변수

int main()
{
    int N, cmd;

    cin >> N;

    f[0] = 1;

    // 팩토리얼 초기화
    for (int i = 1; i < 21; i++)
        f[i] = f[i - 1] * i;

    cin >> cmd;

    // 몇 번째 순열인지 출력하기.
    if (cmd == 2)
    {
        vector<int> a(N);

        // 순열 입력
        for (int i = 0; i < N; i++)
            cin >> a[i];

        long long ans = 0;

        for (int i = 0; i < N; i++)
        {
            for (int j = 1; j < a[i]; j++)
            {
                // 1부터 해당하는 원소까지 팩토리얼 값을 늘려가며 더해준다.
                if (check[j] == false)
                    ans += f[N - i - 1];
            }
            // 순열에 존재하는 숫자는 있다고 표시해준다.
            check[a[i]] = true;
        }

        cout << ans + 1 << "\n";
    }
    // k 번째 순열 출력하기
    else
    {
        long long k;

        cin >> k;

        vector<int> a(N);

        // k번째 순열 찾는 과정
        for (int i = 0; i < N; i++)
        {
            for (int j = 1; j <= N; j++)
            {
                // 순열에 이미 존재하는 숫자면 넘어간다
                if (check[j] == true) continue;
                // 팩토리얼 값이 k보다 작으면 k에서 팩토리얼 값을 빼준다
                if (f[N - i - 1] < k)
                {
                    k -= f[N - i - 1];
                }
                // 팩토리얼 값이 k보다 크면 해당하는 원소의 숫자를 찾은 것. 
                // a[i]에 저장하고 순열에 존재하는 숫자를 체크해준다
                else
                {
                    a[i] = j;
                    check[j] = true;
                    break;
                }
            }
        }

        for (int i = 0; i < N; i++) cout << a[i] << " ";
        cout << "\n";
    }

    return 0;
}