[프로젝트 오일러] 4번 문제 & 풀이 (세자리 수를 곱해 만들 수 있는 가장 큰 대칭수)

Problem 4

앞에서부터 읽을 때나 뒤에서부터 읽을 때나 모양이 같은 수를 대칭수(palindrome)라고 부릅니다.

두 자리 수를 곱해 만들 수 있는 대칭수 중 가장 큰 수는 9009 (= 91 × 99) 입니다.

세 자리 수를 곱해 만들 수 있는 가장 큰 대칭수는 얼마입니까?

처음 아이디어

1. 세 자리 수끼리의 곱의 범위는 (10000, 999999)로 5자리 또는 6자리이다.
2. 대칭수 중 가장 큰 숫자를 묻고 있으므로, 6자리일 확률이 높다.(물론 아닐 수도 있다.)
3. 따라서 큰 수부터 먼저 곱하고 작은 수는 나중에 곱한다.
4. 그 다음, 숫자를 문자열로 변환하여 앞 3자리 숫자를 거꾸로 했을 때, 뒤 3자리 숫자와 같도록 조건문을 작성한다.
5. 6자리 수에서 대칭수가 없을 경우를 대비하여 5자리의 경우의 조건문도 넣는다.

result = []

for i in range(999,100,-1):
    for j in range(999,100,-1):
        num = str(i*j)
        if len(num) == 6:
            a, b, c, d, e, f = num[0], num[1], num[2], num[3], num[4], num[5]
            if a==f and b==e and c==d:
                result.append(int(num))
        elif len(result) == 0:
            a, b, c, d, e = num[0], num[1], num[2], num[3], num[4]
            if a==e and b==d:
                result.append(int(num))
                
print(max(result))

결과 :

906609

 

큰 수부터 안 곱하고, 차례대로 곱했을 경우

result = []

for i in range(100,999):
    for j in range(100,999):
        num = str(i*j)
        if len(num) == 6:
            a, b, c, d, e, f = num[0], num[1], num[2], num[3], num[4], num[5]
            if a==f and b==e and c==d:
                result.append(int(num))
        else:
            a, b, c, d, e = num[0], num[1], num[2], num[3], num[4]
            if a==e and b==d:
                result.append(int(num))

print(max(result))

결과 :

906609

다른 아이디어

1. 숫자가 대칭인 것을 쉽게 판별할 수 있는 식 발견

   if str(num) == str(num)[::-1]: 사용

2. 위 조건을 만족하는 숫자를 리스트에 넣고, 그 중 제일 큰 값이 정답!

result = []

for i in range(100,1000):
    for j in range(100,1000):
        num = i*j
        if str(num) == str(num)[::-1]:
            result.append(num)
            
print(max(result))

결과 :

906609