[Lv 2] 줄 서는 방법

https://school.programmers.co.kr/learn/courses/30/lessons/12936

프로그래머스

 

n개의 숫자 중 k번째에 해당하는 줄서는 방법을 찾아야한다.

초기 첫번째 줄서는 방법으로 배열을 채운다. 이때 k가 1인 경우 줄세운 배열을 그대로 반환한다.

 

이 후 줄세우는 방법의 경우의 수를 알기 위해 dp를 사용해 팩토리얼 연산을 진행한다.

 

1. 4(n)의 값을 사용하면 4(n)개의 숫자 중 앞에 올 숫자.

 div  = 6 / (4!/4)  == 1

mod = 6 % (4!/4) == 0

arr의 div번 째 숫자를 순열에 넣고 arr의 div 요소를 제거.

arr[0]=1

arr[1]=3

arr[2]=4

순열 = {2}

 

2. 3(n-1)개의 숫자 중 앞에 올 숫자.

//위에서 구한 mod를 나누어 준다.

div = 0 / (4!/4/3) ==0

mod = 0 % (4!/4/3) ==0 

arr의 div번 째 숫자를 순열에 넣고 arr의 div 요소를 제거.

arr[0]=3

arr[1]=4

순열 = {2,1}

 

3. 2(n-2)개의 숫자 중 앞에 올 숫자.

//위에서 구한 mod를 나누어 준다.

div = 0 / (4!/4/3/2) ==0

mod = 0 % (4!/4/3/2) ==0 

arr의 div번 째 숫자를 순열에 넣고 arr의 div 요소를 제거.

arr[1]=4

순열 = {2,1,3}

 

4. 마지막 남은 배열의 숫자를 순열에 넣는다.

순열  = {2,1,3,4}

 

https://ongveloper.tistory.com/133

프로그래머스 줄 서는 방법 c++ (구현)

 

#include <string>
#include <vector>

using namespace std;

long long dp[21];
vector<int> solution(int n, long long k) {
    vector<int> answer,v;
    for(int i=1; i<=n;i++){
        v.push_back(i);
    }
    if(k==1)
        return v;
    
    dp[1] = 1;
    for(int i = 2;i<=n;i++)
        dp[i] = i * dp[i-1];
    
    k-=1;
    long long pre = dp[n];
    long long mod,div;

    while(v.size()!=1){
        pre /= n;
        mod = k % pre;
        div = k / pre;
        answer.push_back(v[div]);
        v.erase(v.begin() + div);
        k = mod;
        n--;
    }
    answer.push_back(v[0]);
    return answer;
}