[Programmers] 줄 서는 방법 c++ (구현, 규칙 찾기)

 

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

 

✔ 문제 이해

자연수 n과 k가 주어질 때, 1부터 n까지의 숫자들의 조합 중 k번째의 조합을 구하여라.

 

✔ 풀이 + 코드

next_permutation을 사용하면 시간초과가 난다. -> 규칙을 찾고 최적화를 해야한다.

n가지의 자릿수를 모두 돌면서 구간을 구하고 그 구간에 맞을 때 k를 갱신하며 답을 찾는다. (아래 설명)

 

if n = 4, k = 17 일 때,

1로 시작하는 경우의 수는 3! 가지 ( k = 1~6)

2로 시작하는 경우의 수도 3! 가지 (k = 7~12)

3으로 시작하는 경우의 수도 3! 가지 (k = 13~18)

4로 시작하는 경우의 수도 3! 가지 이다. (k = 19~24)

주어진 k의 범위에 맞는 구간을 찾고, k를 범위보다 한 칸 작은 가장 큰 값으로(6의 배수) 빼준다. (k = 17 - 12 = 5)

 

바뀐 k값과 구간을 이용하여 다시 재귀를 타고 들어가서 모든 자릿수를 다 돌아준다.

3,1로 시작하는 경우의 수는 2! 가지 (k = 1~2)

3,2로 시작하는 경우의 수는 2! 가지 (k = 3~4)

3,4로 시작하는 경우의 수는 2! 가지 (k = 5~6)

k = 5 - 4 = 1

 

3,4,1 로 시작하는 경우의 수는 1가지 (k = 1) 3412 가 정답

3,4,2 로 시작하는 경우의 수는 1가지 (k = 2) 3421

 

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

using namespace std;

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

void func(vector<int>& v, vector<int>& answer, long long& k){
    if(v.size() == 1){
        answer.push_back(v[0]);
        return;
    }

    long long f = facto(v.size()-1);
    for(int i = 1; i <= v.size(); ++i){
        if(f * i >= k){
            answer.push_back(v[i-1]);
            v.erase(v.begin() + i - 1);
            k = k - (i - 1) * f;
            func(v, answer, k);
        }
    }
}

vector<int> solution(int n, long long k) {
    vector<int> answer;

    vector<int> v(n);
    for(int i = 0; i < n; ++i){
        v[i] = i+1;
    }

    func(v, answer, k);
    
    return answer;
}

 

✔ 피드백

존재하는 규칙은 찾았지만 여전히 구현해내는게 어려운것 같다.ㅜㅜ

 

✔ reference

https://ansohxxn.github.io/programmers/105/