Project Euler #40 - Champernowne's constant

프로젝트 오일러 40번

1, 2, ..., 9, 10, 11, 12, ... 이런 숫자들을 쭉~ 붙였을 때 1, 10, 100, ... , 100만번째 나오는 숫자들은? 이 숫자들을 다 곱하면?

넉넉잡아 20만까지 숫자를 붙이면 100만자리는 될거다.

긴숫자, 긴문자에 강한 파이썬의 특성을 살려보면...

irn = ''.join([`n` for n in range(200000)])
print reduce(lambda x, y: x*y, [int(irn[i]) for i in [10**j for j in range(7)]])

0.04초. 이 정도면 괜찮은 듯 하다.

한 줄로 줄이면.. 5배 정도 오래 걸린다. '긴문자'를 반복해서 만들어서 그런가보다.

print reduce(lambda x, y: x*y, [int(''.join([`n` for n in xrange(200000)])[i]) for i in [10**j for j in range(7)]])

메모리 낭비 없이 인덱스를 유지하면서도 해 봤는데 처음보다 20배쯤 오래 걸린다. Not good!

s = n = chk = rs = 1
while chk < 10000000:
    for i in range(1,len(str(s))+1):
        nth = str(s)[i-1]
        if n == chk:
            rs *= int(nth)
            chk *= 10
        n += 1
    s += 1

print rs