[프로그래머스]연습문제 : 줄 서는 방법 (level 3) (c++)

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

코딩테스트 연습 - 줄 서는 방법

 

 

#include <string>
#include <vector>

using namespace std;

long long make_factorial(vector<long long>& fact, long long num)
{
    if (num < 1)
    {
        return 1;
    }
    if (fact[num] > 0)
    {
        return fact[num];
    }

    return fact[num] = make_factorial(fact, num - 1) * num;
}

vector<int> solution(int n, long long k) {
   
    /*
        팩토리얼 배열 만들기. 
        NaN 방지를 위해 0번째 값을 1로 저장해준다.
    */
    vector<long long> fact(n + 1);
    make_factorial(fact, n);
    fact[0] = 1;

    // [1, n]이 저장된 숫자 배열 만들기
    vector<int> nums(n);
    for (int i = 0; i < n; ++i)
    {
        nums[i] = i + 1;
    }

    
    /*
        순열에서 i번째 숫자를 정할 때,
        k가 n - 1자리의 순열을 qe개 가질수 있다면
        i번째 자리 숫자는 현재 남은 숫자 중에서 qe번째로 큰 수 이다.
    */
    --k;
    vector<int> answer;
    while (n--)
    {
        // k를 (n - 1)!로 나누었을 때의 몫과 나머지
        int qe = k / fact[n];
        k %= fact[n];

        // 현재 남은 숫자중에서 qe번째로 큰 수 push
        answer.push_back(nums[qe]);

        // 사용한 숫자는 지워준다.
        nums.erase(nums.begin() + qe);
    }

    return answer;
}

 

 

처음엔 다음순열과 비슷한 문제인줄 알았는데, 전혀 아니었다.

이 문제는 특정 번째의 순열을 주고 다음 순열을 구하라는 것이 아니라,

그냥 처음부터 [1, N]의 숫자로 K번째의 순열을 구하라는 문제이다.

 

다음 순열을 구하는 시간복잡도가 O(N)이므로, 처음부터 순열을 구해나갈 경우

만약 N!번째의 순열을 구하라고 한다면 총 시간복잡도는 O(N! * N)이 된다.

 

 

따라서 다른 방법으로 풀어야 하는데, 풀이 순서는 다음과 같다.

 

1. 순열 생성에 사용할 [1, N]범위의 숫자배열을 만든다.

2. K번째로 오기까지 [1, N - 1]의 순열을 몇 묶음 가질 수 있는지 계산한다.

K / (N - 1)! = Q라면 이 순열은 [1, N - 1]순열을 Q개 거쳤다는 뜻이다.

3. 남아있는 숫자배열 중에서 앞에서 (Q + 1)번째로 큰 숫자를 결과 숫자열에 push한다. 

사용한 숫자는 지워준다.

4. 2~3의 과정을 반복한다.

 

 

글로 풀어쓰니까 오히려 복잡하게 느껴지는데, 2~3의 과정을 코드로 나타내면 다음과 같다.

vector<int> answer;
while (n--)
{
    // k를 (n - 1)!로 나누었을 때의 몫과 나머지
    int qe = k / fact[n];
    k %= fact[n];

    // 현재 남은 숫자중에서 qe번째로 큰 수 push
    answer.push_back(nums[qe]);

    // 사용한 숫자는 지워준다.
    nums.erase(nums.begin() + qe);
}

 

 

2~3의 과정을 예시를 들어 그림으로 나타내면 다음과 같다.

k % (n - 1) = 2 ... 0 이다.

가장 첫번째 자리 숫자는 nums[2]가 되고, 사용한 nums[2]는 지워준다.,

다음번 k는 나머지인 0이 되고, 다음번 n은 1이 된다.

 

k % (n - 1) = 0 ... 0 이다.

두번째 자리 숫자는 nums[0]가 되고, 사용한 nums[0]는 지워준다.

다음번 k는 나머지인 0이 되고, 다음번 n은 1이 된다.

 

k % (n - 1) = 0 ... 0 이다.

세번째 자리 숫자는 nums[0]가 되고, 사용한 nums[0]는 지워준다.

다음번 k는 나머지인 0이 되겠지만, 다음번 n도 0이 되므로 여기서 끝!