Project Euler #4 - largest palindrome product

3자리수 두 개의 곱으로 표현되는 palindrome 숫자(거꾸로 해도 자신과 같은 숫자) 중 가장 큰 것은?

두가지 접근이 가능하다.
1. 최종 숫자를 999999, 998899, 997799 처럼 줄여 나가면서 두 개의 세자리 숫자 곱으로 표현가능한지 찾는 방법
2. 두 개의 세자리 숫자 999*999, 999*998 들을 계산해서 palindrome이 만들어지는지 체크하고, palindrome이면 저장한다. 저장된 숫자들 중 최대값을 찾는다.

첫번째 방법으로 구현해 보았다. 약 1ms 이내.

def pal():
    for e in range(999,100,-1):
        pal = int(str(e) + str(e)[::-1])
        i = pal/999
        while i*i <= pal:
            if pal % i == 0 and pal/i < 1000: return pal
            i += 1

print pal()

두번째 방법도 구현해 보았다. 약 600ms.

palin = []
for i in range(100,1000):
    for j in range(100,i):
        if i*j == int(str(i*j)[::-1]): palin.append(i*j)

print max(palin)

가장 큰 차이는, 첫번째 방법에서는 답을 찾으면 바로 return하고 끝, 두 번째 방법에서는 모든 경우의 수를 따져야 한다는 것이다. 답은 913*993 에서 나오는데, 두번째 방법에서 섣부르게 return 후 break 해 버리면 995*517 이나 924*962 를 피하기 어렵다.


마지막으로, 첫번째 방법에서 while 대신 for loop 을 쓰면 약간이지만 속도가 빨라진다. 매번 조건 체크하는 수고를 덜어서 그런 듯 하다.

def pal():
    for e in range(999,100,-1):
        pal = int(str(e) + str(e)[::-1])
        for i in range(pal/999,int(pal**.5)+1):
            if pal % i == 0 and pal/i < 1000: return i, pal/i, pal

print pal()

ps1. 리스트에 [::-1] 은 거꾸로 한칸씩 이동하라는 뜻 => 리스트를 뒤집는 효과
ps2. from math import sqrt 후에 sqrt(pal) 로 계산한다고 pal**.5 보다 빨라지지 않는다. 괜히 코드만 한 줄 더 길어지고.