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

http://euler.synap.co.kr/prob_detail.php?id=24

Skillist 설명---------------------------------------------------------------------------------

새벽 몇 시간 동안 재미있는 문제였습니다. 

기본 개념 부분과 알고리즘 부분을 직접 작성하여 올립니다.

Skillist 코드---------------------------------------------------------------------------------

public static void main(String[] args){

int array[] = new int[]{0,1,2,3,4,5,6,7,8,9}; //작은 순서대로 숫자 초기화

int number = 1000000; //1000000번째 큰 숫자

int fact=1;

for(int i=1; i<array.length+1;i++){ //10! 계산

fact *= i;

}

for(int i=10;i>0;i--){

fact /= i; //i를 사용하여 순서대로 9!,8!,7!,...,2!,1!,을 만들어 준다.

int j = 0;

while( number > fact ){ //9!,8! 등 각 팩토리얼이 몇번 사용(마이너스) 되는지 확인을 위한 while문

j+=1;

number -= fact;

}

System.out.print(array[j]); //j번에 따라 해당 수 출력

for(int k=j;k<array.length-1;k++){ //사용한 변수 제거 후 배열 재배치

array[k] = array[k+1];

}

}

}

다시 공부---------------------------------------

//다시 공부하며 이해 안되는 부분이 있기 때문에 주석 설명 추가

public static void main(String[] arg){

int[] array={0,1,2,3,4,5,6,7,8,9};

int iWant = 1000000;

int fac = 1;

for(int i=2;i<10;i++){ //9팩토리얼 부터 계산

fac*=i;

}

for(int i=9;i>0;i--){

int where = 0;

while(iWant > fac){ //내가 알기 원하는 숫자가 fac(팩토리얼) 초과일때만 계산해야한다.  같을때 계산하면 클남

where +=1;

iWant -= fac; //나누기는 같을때도 나누기 때문에 -연산을 수행하며 초과 확인.

}

fac/=i;

System.out.print(array[where]); //숫자를 선택해서 출력

for(int j=where;j<array.length-1;j++){ //배열 앞으로 땡기기

array[j] = array[j+1];

}

}

System.out.print(array[0]); //나머지 숫자 출력

}