프로그래머스 Lv2 줄 서는 방법

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

프로그래머스

k번째 순열이 어떤 모습인지 순회하지 않고 바로 알아내는 방법

n = 4, k = 16을 예로 들어보자. 즉 [1, 2, 3, 4]로 이루어지는 순열의 16번째 순열이 어떤 모습인지 규칙을 찾아내보자

• [1, 2, 3, 4] 즉 n =4의 순열은 총 4! = 24가지가 나올 수 있다. 4!는 4*3!와도 같다.
  • [1, 2, 3, 4] 순열 순서의 규칙 (총 4*3! = 24개) [1, 2, 3, 4] 순열 내에서 16번째 찾기
    • 3! = 6개 1로 시작하는 [2, 3, 4]순열 1 ~ 6
    • 3! = 6개 2로 시작하는 [1, 3, 4]순열 7 ~ 12
    • 3! = 6개 3로 시작하는 [1, 2, 4]순열 13 ~ 18
    • 3! = 6개 4로 시작하는 [1, 2, 3]순열 19 ~ 24 
• 16번째 순열은 2x3! < 16 <= 3x3!을 만족하기 때문에 3으로 시작하는 [1, 2, 4]순열에 위치할 것이라는 것을 알 수 있다.
  • 16번째 순열의 첫 번째는 무조건 3이 된다는 것을 확인할 수 있다. 16번째가 3으로 시작하는 순열인 13번째 ~ 18번째에 속하기 때문이다. 이제 [3]은 확정댔으니 남은 [1,2,4]순열 내에서 16 - 12 = 4번째에 해당하는 순열을 찾으면 된다.
    • [1, 2, 4]순열 순서의 규칙(총 3*2! = 6개) [1, 2, 4] 순열 내에서 4번째 찾기
      • 2! = 2개 1로 시작하는 [2, 4]순열 1~2번째
      • 2! = 2개 2로 시작하는 [1, 4]순열 3~4번째
      • 2! = 2개 4로 시작하는 [1, 2]순열 1~2번째
  • 4번째 순열은 1x2! < 4 <= 2x2!을 만족하기 때문에 2로 시작하는 [1, 4] 순열에 위치할 것이라는 것을 알 수 있다.
    • "16번째 순열의 두 번째"는 무조건 2가 된다는 것을 확인할 수 있다. 4번째가 2로 시작하는 순열인 3번째~4번쨰에 속하기 때문이다. 이제 [3, 2]는 확정됐으니 남은 [1,4] 순열 내에서 4-2 = 2번쨰에 해당하는 순열을 찾으면 된다.
      • [1, 4] 순열 순서의 규칙 (총 2* 1!= 2개) [1, 4]순열 내에서 2번째 찾기
        • 1! = 1개 1로 시작하는 [4]순열 1 = (1x1!)번째
        • 1! = 1개 1로 시작하는 [1]순열 2 = (2x1!)번째
      • 2번째 순열은 1x1! < 2 <= 2x1!을 만족하기 때문에 4로 싲가하는 [1] 순열에 위치할 것이라는 것을 알 수 있다!!
        • "16번째 순열의 세 번째"는 무조건 4가 된다는 것을 확인할 수 있다. 2번째가 4로 시작하는 순열인 2번째가 되기 때문이다. 이제 [3, 2. 4]은 확정됐으니 남은 [1]순열 내에서 2 - 2 = 0 번째에 해당하는 순열을 찾으면 된다.
        • "16번째 순열의 마지막 네 번째"는 무조건 1이 된다는 것을 확인할 수 있다. 하나밖에 안 남았기 때문이다. 남은 순열이 [1]하나 남았기 때문에 나머지1을 붙여서 [3, 2, 4, 1]가 완성된다. 이게 바로 16번째 순열이 된다.

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

using namespace std;

long long perm(int n) // n! 값 구하기
{
    if (n == 0) return 1;
    return n * perm(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 p = perm(v.size() - 1); 
    for (int i = 1; i <= v.size(); ++i) {
        if (i * p >= k) {
            answer.push_back(v[i - 1]); // i번째기 때문에 인덱스론 i-1
            v.erase(v.begin() + i - 1);
            k = k - (i - 1) * p;
            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;  // n=4의 경우 v = [1,2,3,4] 에서 시작

    func(v, answer, k);

    return answer;
}

복기를 하면서 경우의 수가 k보다 크거나 같으면서, 현재 조합의 첫번째를 뽑는 다는 것을 헷갈렸다.
확률은 어렵다....