오일러 프로젝트 04

앞에서부터 읽을 때나 뒤에서부터 읽을 때나 모양이 같은 수를 대칭수(palindrome)라고 부릅니다.
두 자리 수를 곱해 만들 수 있는 대칭수 중 가장 큰 수는 9009 (= 91 × 99) 입니다.
세 자리 수를 곱해 만들 수 있는 가장 큰 대칭수는 얼마입니까?

접근

대칭수를 판단하는 방법은 크게 두 가지가 있다.

1. 문자열로 변환한 후, 원래의 문자열과 뒤집은 문자열이 같은지를 본다.
2. 각 자리 수의 리스트로 변환한 후, 역시 뒤집은 리스트와 같은지를 본다.

뒤집은 문자열이나 뒤집은 리스트는 xs[::-1] 로 확인하는 것이 파이썬에서는 가장 빠르다.

풀이

from itertools import combinations

def is_palindrome(n: int) -> bool:
  res = []
  while n > 0:
    n, q = divmod(n, 10)
    res.append(q)
  return res == res[::-1]

def main():
  return max(x * y for (x, y) in combinations(range(100, 1000), 2) if is_palindrome(x*y))

두 개의 세자리 정수의 곱을 구하려할 때, 123 * 321 은 321 * 123 과 동일하므로 이 중 루프를 돌기 보다는 세자리 수의 중에서 2개씩 조합을 구해서 계산하면 범위를 더 줄일 수 있다. 또 세 자리 수 두 개의 곱은 최대 6자리의 수를 만들 수 있다. 따라서 우리가 구하고자 하는 가장 큰 값은 6자리 대칭수가 될 것이고, 두 수의 곱은 전체 범위의 상위 절반에 있는 값에서 생성될 가능성이 크다. 따라서 100~999 범위가 아닌 555~999 범위에서 조합을 구해도 된다.