프로그래머스 - 줄 서는 방법(C++)

문제 출처: https://programmers.co.kr/learn/courses/30/lessons/12936

문제 난이도

Level 3

문제 접근법

수학적 사고를 해야하는 문제 -> 효율성 문제가 있기 때문에
먼저 N까지 나오는 경우의 수를 따져서 크게 나뉘는 수를 생각해야 한다.

배열 [1,2,3] 기준으로
K=5 (이지만 5로 기준으로 K/N(3)을 한다면 Index 번호가 맞지 않기 때문에 K--를 해준다. 즉, K=4라고 생각하자)
전체 경우의 수를 N!이 나온다 하면 각각의 차례대로 숫자가 가지고 있는 집합은 N을 나누어주면 몇 집합인지 나오기 때문에 N-1!이 된다.
그렇게 맨 앞자리수는 K/F(2) 인 Index==2인 3이되고, K는 K %=F(2)로 인해 0이 나온다.
Index==0은 1이되고, 그리고 다음 Index == 0인데 이때 erase함수를 사용해 지우기 때문에 배열 0번 인덱스는 1번이었던 인덱스가 앞으로 땡겨져 2가 나온다.

통과 코드

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

long long factorial[21] = {1,};

vector<int> solution(int n, long long k) {
	vector<int> answer,init;
    long long now = 0;
	for (int i = 1; i <= n; i++) {
		factorial[i] = factorial[i - 1] * i;
		init.push_back(i);
	}
    k--;
	while(n>0){
        now = k/factorial[n-1];
        answer.push_back(init[now]);
        init.erase(init.begin()+now);
        k %= factorial[n-1];
        n--;
    }

	return answer;
}

피드백

처음에는 이렇게 풀었는데 효율성 테스트를 통과하지 못했다.

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

long long factorial[21] = {1,};
vector<vector<int>> res;
bool ch[21];
vector<int> init;

void dfs(int cnt,  vector<int> a, int n) {
	if (cnt == n) {
		res.push_back(a);
		return;
	}
	for (int i = 0; i < n; i++) {
		if (ch[init[i]]) continue;
		ch[init[i]] = true;
		a.push_back(init[i]);
		dfs(cnt + 1,  a, n);
		ch[init[i]] = false;
		a.pop_back();
	}
}

vector<int> solution(int n, long long k) {
	vector<int> answer;
	for (int i = 1; i <= n; i++) {
		factorial[i] = factorial[i - 1] * i;
		init.push_back(i);
	}
	long long start = (k - 1) / factorial[n - 1];
	long long etc = (k - 1) % factorial[n - 1];
	ch[init[start]] = true;
	vector<int> a;
	a.push_back(init[start]);
	dfs(1, a, n);
	answer = res[etc];

	return answer;
}

그리고 다른 사람 코드를 참고해서 고침 ..ㅠ