Project Euler #36 - 거꾸로 해도 같은 수

프로젝트 오일러 36번
100만 이하의 수 중에서, 10진수로 하든 2진수로 하든 거꾸로 해도 자기자신이 되는 수를 모두 더하면?

33 = 100001 (2) 같은 것도 되지만, 313 = 100111001 같은 경우도 고려해야 한다.

def d2b(d):
    b = ''
    while True:
        b += str(d%2)
        d /= 2
        if d == 0: return b == b[::-1]

sm = 0
for i in ['']+[str(x) for x in range(1,1000)]:
    for j in ['']+[str(x) for x in range(10)]:
        s = str(i)+str(j)+str(i)[::-1]
        if len(s) >= 1 and len(s) <= 6:
            pd = int(s)
            if d2b(pd):
                sm += pd

print sm

0.03~0.05초 정도 걸린다.

d2b함수는 10진수를 2진수(정확히는 2진수를 거꾸로 쓴 수)를 찾고 그게 palindrome인지 체크한다.
i는 10진수로 했을 때 왼쪽 절반을, j는 가운데 숫자를 의미한다.
i=58, j=3 => 58385
i = 2, j='' => 22
i = '', j=7 => 7

컴퓨터 내부적으로는 2진수가 기본일테니 여기에서처럼 10진수를 2진수로 바꾸는 대신, 2진수를 기본으로 palindrome을 만들고, 조건에 맞을 때 10진수로 변환해서 palindrome인지 체크하는 게 더 빠를 것 같은데.. 어떻게 하는지도 모르겠고, 지금 속도도 문제가 되지 않는 듯 해서 패쓰~

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 보다 빨라지지 않는다. 괜히 코드만 한 줄 더 길어지고.