[Project Euler] 24. 0, 1, 2, 3, 4, 5, 6, 7, 8, 9로 만들 수 있는 1,000,000번째 사전식 순열은?

24. 0, 1, 2, 3, 4, 5, 6, 7, 8, 9로 만들 수 있는 1,000,000번째 사전식 순열은?

어떤 대상을 순서에 따라 배열한 것을 순열이라고 합니다. 예를 들어 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번째는 무엇입니까?

Click

일일이 순열을 다 구해서 하면... 최대 10!의 loop를 돌아야 하겠지만... 조금만 생각하면 쉽게 구할 수 있는 방법이 나오는 군요.

10개의 수로 표현할 수 있는 순열의 수는 10!.
1개를 골랐다고 했을 때 나머지로 나타낼 수 있는 조합은 9!, 8!, 7! ...... 1! 
처음 n을 9!로 나눈 값이 첫번째 오는 수.
그리고 n을 9!로 나눈 나머지 값을 8!로 나눈 값이 첫번째 구한 수를 빼고 남은 숫자중에 몇번째 수인지를 나타내고...
이런식으로 10번의 과정을 반복하면 원하는 결과를 얻을 수 있음.

간단하게 도출한 알고리즘에 따라 코드로 구현을 하면....

<script>
function p024_1(n){
    var arr = new Array(true,true,true,true,true,true,true,true,true,true);
    
    var s = 10 * 9 * 8 * 7 * 6 * 5 * 4 * 3 * 2 * 1;
    if(s < n) return '최대 수를 초과하였습니다.';
    var temp = n-1;
    var r = 0;
    for(var i=10; i>0; i--){
        s /= i;
        for(var j=0; j<i; j++){
            if(temp<s){
                var t = 0;
                for(var k=0; k<10; k++){
                    if(t==j && arr[k]){
                        r = r*10 + k;
                        arr[k] = false;
                        break;
                    }
                    if(arr[k])
                        t++;
                }
                break;
            }
            temp -= stand;
        }
    }
    return r;    
}
</script>

첫번째 코드입니다. for문이 3개나 되서 loop가 많다고 생각 할 수 있지만... for문 하나는 if문 안에 있다는 것을 알 수 있죠. 대충 보면 최악의 경우.... 2*10+2*9+2*8+2*7+2*6+2*5+2*4+2*3+2*2+2*1 = 110번 정도의 loop를 돌 것 같네요. 그리고 이걸 수정한 코드가...

<script>
function p024_2(n){
    var arr = new Array(true,true,true,true,true,true,true,true,true,true);
    
    var s = 10 * 9 * 8 * 7 * 6 * 5 * 4 * 3 * 2 * 1;
    if(s < n) return '최대 수를 초과하였습니다.';
    var temp = n-1;
    var r = 0;
    for(var i=10; i>0; i--){
        s /= i;
        var k = parseInt(temp/s);
        temp = temp%s;
        var t=0;
        for(var j=0; j<10; j++){
            if(t==k && arr[j]){
                r = r*10 + j;
                arr[j] = false;
                break;
            }
            if(arr[j])
                t++;
        }
    }
    return r;
}
</script>

이 코드입니다.
for문을 하나 없애서.... 이것도 최악의 경우.... 55회의 loop를 돌겠네요.