[프로그래머스 2레벨] 줄 서는 방법 (C++)

#include <string>
#include <vector>

using namespace std;

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

    //팩토리얼 계산
    for (int i = 1; i < n; i++) fac[i] = fac[i - 1] * i;

    for (int i = 1; i <= n; i++) v.push_back(i);
    
    k--;
    // 4. k번째 순열 찾기 (k-1)/(n-1)!
    for (int i = n - 1; i >= 0; i--) {
        int idx = k / fac[i];  //위치
        answer.push_back(v[idx]);
        v.erase(v.begin() + idx);  //찾은 값 삭제
        k %= fac[i];  //k값 조정
    }

    return answer;
}

 

먼저 가능한 케이스를 통해 규칙을 찾아보자.

1 : 1

2 : 1 2 / 2 1

3 : 1 2 3 / 1 3 2 / 2 1 3 / 2 3 1 / 3 1 2 / 3 2 1

4 : 1 2 3 4 / 1 2 4 3 / 1 3 2 4 / 1 3 4 2 / 1 4 2 3 / 1 4 3 2 / ....

 

맨 첫 번째 숫자가 오는 경우를 보면

1의 경우 1개, 2의 경우 1개씩, 3의 경우 2개씩, 4의 경우 6개씩으로 (n-1)!인 것을 알 수 있다.

그 다음 위치 숫자의 경우에는 (n-2)!이고, 그이후로 1씩 줄어서 (n-3)!, (n-4)! 이런식으로 경우의 수를 갖는다.

 

따라서 먼저 팩토리얼을 따로 계산하여 담아주었다.

또한 가능한 숫자인 1~N까지를 담은 벡터 또한 선언해주었다.

 

이제 k번째 순열 찾기이다.

앞서 첫 번째 숫자가 오는 케이스에 대해 n!인 것을 알았기에, k/n!을 해주면 첫 번째 숫자의 경우를 알 수 있다.

다만 이때 인덱스를 맞추기 위해 k값을 그대로 쓰는 것이 아닌, 1을 빼서 (k-1)/(n-1)!을 계산주어야 한다.

앞서 찾았던 규칙을 통해 반복문을 n-1부터 시작하여 1씩 감소시키는 것으로 해당 위치에 대한 값을 탐색해나간다.

 

이제 위치를 알았기에 해당 위치를 기준으로 기존에 숫자를 담아준 벡터에서 해당 위치에 맞는 값을 찾아주고, 

찾았으면 이제 사용되어 다음 위치에선 선택 불가하기에 삭제해준다.

 

이제 k 값을 조정하여 다음 위치에 대해 탐색해야한다.

이때는 k%=fac[i]를 이용하여 값을 조정하게 된다.

해당 예시의 경우 4%2=0이 되고, 0은 첫 번째를 나타내므로 1을 가리키게 된다.