[프로그래머스 Level 2] 줄 서는 방법(C++)

코딩테스트 연습 - 줄 서는 방법 | 프로그래머스 스쿨 (programmers.co.kr)

프로그래머스

완전탐색으로 하기에는 n의 수가 20이므로 무조건 시간초과가 날 수 밖에 없다. 따라서 한 자리씩 수를 정해주는 방식으로 구현해보았다. 예를 들어, 맨 첫 자리를 1이라고 쳤을 때의 나오는 경우의 수는 (N-1)!이다. 만약 이 수가 K보다 크면 첫 자리를 1이라고 두고 다음 자리의 숫자를 찾아야 한다. 하지만 K보다 작으면 (N-1)!의 값을 K에서 빼주고 첫 자리를 2로 둔 다음 다시 계산해줘야한다. 이와 같은 방식으로 모든 자리의 숫자를 정해줘야 한다.

#include <string>
#include <vector>

using namespace std;

string num = "";
bool arr[21];
long long K;
int N;

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

void rec(int dep) {
	if (dep == N+1)
		return;
	for (int i = 1; i <= N; i++) {
		if (arr[i])
			continue;
		long long val = factorial(N - dep);
		if (val < K) {
			K -= val;
		}
		else {
			num += i + '0';
			arr[i] = true;
			rec(dep + 1);
		}
	}
}

vector<int> solution(int n, long long k) {
	vector<int> answer;
	K = k;
	N = n;
	rec(1);
	for (int i = 0; i < num.size(); i++) {
		answer.push_back(num[i]-'0');
	}
	return answer;
}