[C++] 백준 1722번 순열의 순서

문제 링크

1722번: 순열의 순서

문제 요약

1부터 N까지의 수에 대해서 다음 두 가지 중 하나를 구한다.
1. 입력받은 수열이 몇 번째 순열인지
2. K번째 순열

접근 방법

std::next_permutation을 안다면 std::next_permutation을 K번 호출하는 풀이를 생각해 볼 수도 있습니다. 하지만 이 문제의 N은 최대 20이고 $20!$은 대략 $2.432902e+18$ 정도이기 때문에 시간초과가 날 수밖에 없습니다.

따라서 몇번째 순열인지 직접 추적하되 중간 과정은 팩토리얼을 이용해서 넘기는 식으로 답을 구해야 합니다.

3 2 4 1

위의 수열이 몇 번째 순열인지 구하는 과정을 생각해보겠습니다.

List : [1, 2, 3, 4]
Now : [?, ?, ?, ?]
Target : [3, 2, 4, 1]

위에서부터 차례로

1. 사용되지 않은 수의 리스트
2. 현재 만들고 있는 순열의 상태
3. 만들고자하는 순열입니다.

여기서 Now의 첫 자리에 들어와야하는 수는 Target에서 볼 수 있듯이 3입니다. 이 3이라는 수는 List의 세번째 원소입니다. 그렇기 때문에 적어도 현재 자리에 1 또는 2가 오는 순열들은 모두 건너뛸 수가 있습니다.

맨 앞 자리 숫자를 임의의 수로 고정시키면 남은 자리는 3개가 되고, 세 개의 수로 만들 수 있는 순열의 수는 $3!$이 됩니다. 따라서 현재 자리의 숫자가 3인 순열은 적어도 현재 자리가 1 또는 2인 순열의 수인 $2\times3!$보다는 크다는 것을 알 수 있습니다. 이 $2\times3!$를 결과에 더해줍니다.

List : [1, 2, 4]
Now : [3, ?, ?, ?]
Target : [3, 2, 4, 1]

Now의 맨 앞 자리를 3으로 갱신한 상태입니다. 따라서 List에서는 3이 제거되었습니다.
이번에 Now의 두번째 자리에 와야할 수는 2로, List의 두번째 원소입니다. List에서 2보다 작은 수인 1이 현재 자리에 오는 경우 만들 수 있는 순열의 수는 $1\times2!$개 입니다.

List : [1, 4]
Now : [3, 2, ?, ?]
Target : [3, 2, 4, 1]

List : [1]
Now : [3, 2, 4, ?]
Target : [3, 2, 4, 1]

List : []
Now : [3, 2, 4, 1]
Target : [3, 2, 4, 1]

절차를 반복하면 결과적으로 Now와 Target이 같아지게 됩니다.

매 반복마다 (넣어야 하는 숫자의 리스트에서의 위치) * (남은 자리 수)!을 더해주면 몇번째 순열인지 구할 수 있습니다.

마찬가지로 이 절차를 응용하면 다른 질의 역시 해결할 수 있습니다.

코드

#include <bits/stdc++.h>
#define VPRT(x, type) copy(x.begin(), x.end(), ostream_iterator<type>(cout, " "))
#define ALL(x) x.begin(), x.end()
#define FASTIO ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define endl '\n'

using namespace std;

long long factorial(int num)
{
	long long ret = 1;
	for (int i = 1; i <= num; i++)
		ret *= (long long)i;
	return ret;
}

int main(void)
{
	FASTIO;

	int n, q;
	cin >> n >> q;

	list<int> ls;
	for (int i = 1; i <= n; i++)
		ls.push_back(i);

	if (q == 1)
	{
		long long k;
		cin >> k;

		vector<int> res;
		for (int i = 1; i <= n; i++)
		{
			long long num = factorial(n - i);		
			for (list<int>::iterator it = ls.begin(); it != ls.end(); it++)
			{
				if (k - num <= 0)
				{
					res.push_back(*it);
					ls.erase(it);
					break;
				}
				k -= num;
			}
		}

		VPRT(res, int);
	}
	else
	{
		vector<int> v(n + 1);
		for (int i = 1; i <= n; i++)
			cin >> v[i];

		long long res = 0;
		for (int i = 1; i <= n; i++)
		{
			long long num = factorial(n - i);
			for (list<int>::iterator it = ls.begin(); it != ls.end(); it++)
			{
				if (*it == v[i])
				{
					ls.erase(it);
					break;
				}
				res += num;
			}
		}
		cout << res + 1;
	}

	return 0;
}