[PE] Project Euler 32

[python] string을 list()하면 어떻게 될까? 글에서 이어서, 

 

문제 링크는 프로젝트 오일러 32번.

 

39 × 186 = 7254 같이, 곱하는 두 수와 곱한 결과에 1부터 9까지 숫자가 다 들어가는 경우를 찾으면 되는데, 이게 뜻하는 것은 결국 str(i) + str(j) + str(i*j)의 결과에 1부터 9까지 숫자가 모두 포함되어 있다는 것과 같다.

그런데 위에서 string을 list로 바꾸는 것이 쉽게 가능함을 보았으니, 이를 바로 활용하면

sorted(list(str(i)+str(j)+str(i*j))) == list('123456789')

이 조건이 true인 경우를 찾는 문제로 바뀐다. i, j중 작은 숫자가 100 이상일 경우, 3자리수 * 3자리수가 최소 5자리수이므로, 총 숫자 개수가 11개 이상이 되어버려 조건을 만족할 수 없다는 것까지 관찰했다면, 이 문제는 아래와 같이 접근할 수 있다.

s = []
for i in range(1,100):
    for j in range(i, 123456789):
        if len(str(i)+str(j)+str(i*j))>9: break
        if sorted(list(str(i)+str(j)+str(i*j))) == list('123456789'):
            print(i,j,i*j)
            if i*j in s: continue
            s.append(i*j)
print(s)
print(sum(s))

 

j 범위가 커보이지만, 어차피 j가 다섯자리 이상 수가 되면 1자리수 * 5자리수 = 5자리수 이상이 되어 break문에 걸려 다음 i로 넘어간다. 즉, 루프를 최대 10^2 * 10^4 = 10^6회 밖에 돌지 않는 것. 이렇게 하면 무리 없이 답을 구할 수 있다.