Project Euler #62 - 세제곱 순열

프로젝트 오일러 62번 - cubic permutations

345^3 = 41063625 의 자리수를 바꾸면, 56623104 = 384^3 도 되고, 66430125 = 405^3도 된다. 실제로, 345^3은 이런 성질을 갖는 가장 작은 수이다.
5개의 permutation을 갖는 가장 작은 세제곱수는?


계속 문제가 길어지고 코드는 지저분해져서 재미가 떨어지고 있었는데 오랜만에 쉽게 풀리는 문제를 만났다. 60번, 61번에서 시간을 너무 많이 써서 더 그런 느낌..

그냥 n=1,2,3,4,5.. 에 대해 세제곱수들의 개수를 세다가 5가 되면 return. 단, permutation에 invariant하게 저장해야 하므로 각 자리수의 숫자들을 정렬하여 숫자를 세었다.

n = 1
rs = {}
while True:
    tmp = ''.join(sorted(`n**3`))
    if tmp in rs: rs[tmp].add(n)
    else: rs[tmp] = {n}
    if len(rs[tmp]) == 5:
        print min(rs[tmp])**3
        break
    n += 1

0.05초.
좀 걸리는 부분이 있다. 문제에서 "which exactly five"라고 했는데 위의 코드로는 6개가 되어도 5개 찾은 순간 return하게 된다. 엄밀하게 하려면, 자리수가 바뀌기 전까지 break하지 말고 계속 체크해야 하지만.. five permutations도 매우 드문데, 갑자기 six permutations는 되지 않을 것 같아서 굳이 코드에 넣지 않았다.