[C++]프로젝트 오일러 24번 문제&풀이 (0, 1, 2, 3, 4, 5, 6, 7, 8, 9로 만들 수 있는 1,000,000번째 사전식 순열은?)

문제 24번

어떤 대상을 순서에 따라 배열한 것을 순열이라고 합니다. 예를 들어 3124는 숫자 1, 2, 3, 4로 만들 수 있는 순열 중 하나입니다.

이렇게 만들 수 있는 모든 순열을 숫자나 문자 순으로 늘어놓은 것을 사전식(lexicographic) 순서라고 합니다.
0, 1, 2로 만들 수 있는 사전식 순열은 다음과 같습니다.

012   021   102   120   201   210

0, 1, 2, 3, 4, 5, 6, 7, 8, 9로 만들 수 있는 사전식 순열에서 1,000,000번째는 무엇입니까?

 

접근방법

1. 팩토리얼 함수를 정의한다.(0! = 1  //  n! = n * (n-1) * ... * 1)

2. numVec에 0~9까지의 숫자를 담고, 1000000번째의 숫자를 계산해보자.

3. 먼저 첫번째 올 숫자(10^9의 자리)를 정해야 하는데, 첫번째 자리를 제외한 나머지 아홉개 숫자 배열들의 경우의 수는 9!이다.

4. 1000000을 count에 담고, 9!보다 크면 첫번째 숫자를 numVec 0번째 칸에서 한칸 옆으로 이동시키고, count = count - 9!를 해준다.

5. 이와같은 방식으로 count가 9!가 작아지면 그때의 숫자가 10^9의 자리의 수이다.(여기서는 2)

6. 이제 2를 conVec에 담아주고, numVec에서는 빼준다.

7. 이제 두번째 올 숫자(10^8의 자리수)를 구해야 하는데, 나머지 여덟개 숫자 배열들의 경우의 수는 8!이다.

8. 3~6번과 같은 방식으로 계속 반복하여, 최종적으로 conVec에 담겨있는 배열 순서가 1000000번째 수가 된다.

#include <iostream>
#include <vector>

using namespace std;

int factorial(int num)
{
    int result = 1;

    if (num < 0) return 0;
    else if (num == 0) return result;
    else
    {
        for (int i = 1; i <= num; i++)
        {
            result = result * i;
        }
        return result;
    }
}

int main()
{
    vector<int> numVec = { 0,1,2,3,4,5,6,7,8,9 };
    vector<int> conVec;

    int count = 1000000;

    for (int k = 1; k <= 10; k++)
    {
        //cout << factorial(numVec.size() - 1) << endl;

        int n = 0;

        while (count > factorial(numVec.size() - 1)) // 9! ~ 1!
        {
            if (count > factorial(numVec.size() - 1))
            {
                count -= factorial(numVec.size() - 1);

                //cout << k << " " << numVec[n] << " " << count << endl;

                n++;
            }
            else
                break;
        }

        conVec.push_back(numVec[n]);
        numVec.erase(numVec.begin() + n);

        //cout << endl;
        //cout << endl;
    }

    cout << "Answer is : ";

    for (int i = 0; i < conVec.size(); i++)
    {
        cout << conVec[i];
    }

    cout << endl;

    return 0;
}

참고

https://github.com/mannlim/ProjectEuler

mannlim/ProjectEuler