앞에서부터 읽을 때나 뒤에서부터 읽을 때나 모양이 같은 수를 대칭수(palindrome)라고 부릅니다.
두 자리 수를 곱해 만들 수 있는 대칭수 중 가장 큰 수는 9009 (= 91 × 99) 입니다.
세 자리 수를 곱해 만들 수 있는 가장 큰 대칭수는 얼마입니까?
접근
대칭수를 판단하는 방법은 크게 두 가지가 있다.
- 문자열로 변환한 후, 원래의 문자열과 뒤집은 문자열이 같은지를 본다.
- 각 자리 수의 리스트로 변환한 후, 역시 뒤집은 리스트와 같은지를 본다.
뒤집은 문자열이나 뒤집은 리스트는 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 범위에서 조합을 구해도 된다.