[오일러프로젝트] 62번문제

세제곱수인 41063625 (=345³) 로 순열을 만들어보면, 그 중에서 56623104 (=384³)와 66430125 (=405³)가 또 세제곱수입니다.
실제 41063625은, 자릿수로 만든 순열 중에서 3개가 세제곱수인 가장 작은 수입니다.

그러면 자릿수로 만든 순열 중에서 5개가 세제곱수인 가장 작은 숫자는 무엇입니까?

처음에 순열이라는 단어에 혹해서
n**3인 dict를 생성하고, 각 n**3의 순열 리스트를 구해서 5개가 되는지

하나하나 찾아가는 로직으로 구현했는데 속도가 너무 떨어졌다. 생각해보니 순열이라는것이

결국은 sort하면 같은 수가 되는 애들이라..

57623의 다른 순열 23675가 있을 때 이 두 수를 정렬시키면

23567로 같은 수를 가지게 되는 것... 이것을 사용해서 n**3의 값을 정렬하여 같은 값을 갖는

애들끼리(순열) 모았음....

Python

	def get_answer():
	cubic_map=dict()
	for n in range(0,100000):
	k="".join(sorted(str(n**3)))
	if not k in cubic_map:
	cubic_map[k]=list()
	cubic_map[k].append(n**3)
	else:
	cubic_map[k].append(n**3)
	for k in cubic_map.keys():
	if len(cubic_map[k]) == 5:
	print (cubic_map[k])
	break
	if __name__ == "__main__":
	get_answer()
	else:
	import itertools
	permutations = list(itertools.permutations(list("41063625"), len("41063625")))
	p=set()
	for t in permutations:
	s="".join(n for n in t)
	p.add(int(s))
	for k in p:
	if k == 41063625:
	print(k)

view raw 62.py hosted with ❤ by GitHub

순열=itertools라는 이 공식이 머리속에 박혀버린듯..-.-