문제 정보

난이도: lv2

n명의 사람이 일렬로 줄을 서고 있습니다. n명의 사람들에게는 각각 1번부터 n번까지 번호가 매겨져 있습니다. n명이 사람을 줄을 서는 방법은 여러가지 방법이 있습니다. 예를 들어서 3명의 사람이 있다면 다음과 같이 6개의 방법이 있습니다.

[1, 2, 3]
[1, 3, 2]
[2, 1, 3]
[2, 3, 1]
[3, 1, 2]
[3, 2, 1] 사람의 수 n과, 자연수 k가 주어질 때, 사람을 나열 하는 방법을 사전 순으로 나열 했을 때, k번째 방법을 return하는 solution 함수를 완성해주세요.

제한 사항

n은 20이하의 자연수 입니다.
k는 n! 이하의 자연수 입니다.

도출 과정

맨 처음에 풀었을 때는 습관처럼 Brute force로 풀었었다. 사실 20!이면 꽤 큰 수이긴 하다. Brute force로 tree형태로 계속 경우의 수를 구하다 보면 구해지긴 한다. 하지만 n이 20일 때 마지막 번째를 구하게 되면 20!이나 되는 경우의 수를 구해야 한다. 이런 경우 다른 방식으로 구해야 하는데 순서가 사전식으로 나열한다는 것이 힌트가 되었다.
사전식으로 나열하게 되면 맨 앞자리는 (n-1)!만큼 반복되는 것을 알 수 있다. 따라서 l번째 숫자는 (n-l)!번 반복된다는 것을 알 수 있고 구하고자 하는 위치를 k라고 하면 l번째 에서는 k/(n-l)!번째 문자가 온다는 것을 알 수 있다. (1번째 이후에는 k를 (n-l)!만큼 나누어 주어야 한다)
따라서 팩토리얼만 알고 있다면 어떤 위치에 어떤 문자가 위치하는지 알 수 있다.

알고리즘

#include <string>
#include <vector>

using namespace std;

long long facts[21];
vector<int> solution(int n, long long k) {
    vector<int> answer;
    vector<int> ser(n);

	facts[1] = 1;
	for (int i = 2; i <= 20; i++)
		facts[i] = facts[i - 1] * i;
	
	for (int i = 0; i < n; i++) {
		ser[i] = i + 1;
	}

	long long rem = k - 1;
	for (int i = 1; i < n; i++) {
		int cnt = 0;
		int idx = rem / facts[n - i];
		int flag = 0;

		rem = (rem % facts[n - i]);
		for (int j = 0; j < n && flag == 0; j++) {
			if (ser[j] != -1) {
				if (cnt == idx) {
					answer.push_back(ser[j]); 
					ser[j] = -1;
					flag = 1;
					break;
				}
				else {
					cnt++;
				}
			}
		}
	}

	for (auto n : ser) {
		if (n != -1)  {
			answer.push_back(n);
			break;
		}
	}

    return answer;
}

먼저 구현하기 전에 factorial를 다 구해 놓았다. 제한 사항이 20까지므로 20까지만 구하였다. 그리고 같은 문자를 반복하여 사용할 수 없으므로 어떤 문자를 사용했는지 알기 위한 벡터 ser를 두었다. 구해진 factorial를 기반으로 필요한 문자열 위치를 알아내고 사용한 문자를 체크하면서 반복하게 되면 결국 k번째의 값을 구할 수 있다.

  • 알고리즘: 구현