줄 서는 방법/C++

프로그래머스

 

• n명이 줄을 설 수 있는 방법은 총 n!개이다.
• i x (n-1)!을 통해 몇 번째 숫자가 올 것인지 알 수 있다.

vector형 v를 선언하고 v에 1부터 n까지의 숫자를 담는다. 그리고 n!을 구하는 함수를 작성하고 줄을 서는 n!개의 방법 중 k번째 방법을 구하는 함수를 작성한다.

k번째 방법을 구하는 함수에서 만약 v의 크기가 1이라면 마지막 숫자만 남은 것이므로 answer에 v[0]를 담고 리턴한다.

아니라면 위에서 작성한 함수로 (v.size() - 1)!을 구하고 1부터 v.size()까지 반복문을 돌며 i x (v.size() - 1)!이 k보다 커진다면 answer에 v[i-1]을 담고 v에서 삭제한 후 k에 k에서 (i-1) x f을 뺀 값을 대입한다. 그리고 func2를 다시 수행한다.

재귀가 끝난 후 answer를 리턴한다.

 

#include <string>
#include <vector>

using namespace std;

long long func1(int n) {
    if(n == 0) return 1;
    return n*func1(n-1);
}

void func2(vector<int>& v, vector<int>& answer, long long& k) {
    if(v.size() == 1) {
        answer.push_back(v[0]);
        return;
    }
    
    long long f = func1(v.size() - 1);
    for(int i = 1; i <= v.size(); i++) {
        if(i * f >= k) {
            answer.push_back(v[i - 1]);
            v.erase(v.begin() + i - 1);
            k = k - (i - 1) * f;
            func2(v, answer, k);
        }
    }
}

vector<int> solution(int n, long long k) {
    vector<int> answer;
    vector<int> v;
    
    for(int i = 1; i <= n; i++) 
        v.push_back(i);
    
    func2(v, answer, k);
    
    return answer;
}