Project Euler #24 - 100만번째 permutation

0~9의 permutation 으로 만들 수 있는 숫자들을 차례로 늘어놓았을 때, 100만번째 수는?

1번째는 0123456789

9!+1번째는 1023456789

9!*2+1번째는 2013456789

그럼 제일 앞에 2를 고정하고, 9개의 숫자로 permutation을 만들었을 때  100만 - 9!*2 번째 숫자를 찾는 문제로 바뀐다.

코드로 표현하면,

factorial = {1:1}
for i in range(2,10):
    factorial[i] = i*factorial[i-1]

answer = ''
d = range(10)
N = 1000000-1
for i in range(9,0,-1):
    answer += str(d.pop(N / factorial[i]))
    N %= factorial[i]

print answer + str(d[0])