프로젝트 오일러 004

문제

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

4번 문제

세자리 수를 곱해 만들 수 있는 가장 큰 대칭수

사이냅소프트

대칭수

어떤 정수 n이 대칭수인지 알아내려면, 각각의 자리 숫자의 리스트로 분해한 다음, 그것이 대칭인지를 알아보면 됩니다. 대칭인지를 알아보는 방법은 다양합니다. reversed() 함수로 리스트를 뒤집을 수 있으니, 그 방법을 쓸 수도 있겠죠.

n = 95759
numbers = []
while n > 0:
  n, m = divmod(n, 10)
  numbers.append(m)

u = list(reversed(numbers))
if u == numbers:
  print("Palindrome")
else:
  print("Nope")

하지만 보통 어떤 연속열을 뒤집는 가장 좋은 방법은 슬라이스 문법을 사용하는 것입니다. 슬라이스 문법은 파이썬에서 내부적으로 C코드로 돌아가기 때문에 아주 빠릅니다.

그리고, 굳이 정수를 리스트로 분해할 필요도 없습니다. 문자열도 연속열이므로 슬라이스 문법으로 뒤집을 수 있습니다. (단, 뒤집으면 한 글자의 튜플이 되므로, 다시 붙여줘야 합니다.)

n = 95759
s = str(n)
if s == ''.join(s[::-1]):
  print("Palinrome")
else:
  print("Nope")

이쯤 되면 대칭수인지 검사하는 함수를 한 줄로 작성할 수도 있겠네요.

풀이

여기서는 '가장 큰 수'를 찾으라고 했습니다. 보통 가장 큰 수를 알기 위해서는 전수 조사를 해야 합니다. 따라서 세 자리 수를 곱해서 만들 수 있는 모든 대칭수를 알아낸 다음 그 중에서 가장 큰 것을 고를겁니다.

세 자리 자연수는 100부터 999까지 900개가 있습니다. 100 × 100 부터 999 × 999까지는 모두 810,000 개의 숫자가 있습니다만, 실제로는 곱셈에 순서가 없으므로 그 절반인 405,000 가지 경우를 검사하면 됩니다.

ispal = lambda n: str(n) == ''.join(str(n)[::-1])
pals = set()
for x in range(100, 1000):
  for y in range(x, 1000):
    z = x * y
    if ispal(z):
      pals.add(z)
print(max(pals))

이 외에 다른 해법도 있습니다. 가장 큰 6자리 수부터 거슬러 내려오면서, 대칭수인지, 대칭수라면 두 개의 세 자리 수의 곱으로 나타낼 수 있는지를 검사하면 됩니다.

왠지 복잡해 보이지만, '가장 큰 대칭수'를 찾기 때문에 가장 큰 수부터 내려오면서 조건을 만족하는 첫번째 수를 찾으면 됩니다. 그러면 전수조사보다 더 빨리 답을 찾을 수도 있습니다. 앞 문제에서 살펴본 '인수의 성질'을 이용하면 3자리 수 두 개의 곱인지 여부를 찾는 것도 생각보다 준수하게 만들 수 있습니다.

def d3(n: int) -> bool:
  for m in range(100, int(n**0.5 + 1)):
    x, y = divmod(n, m)
    return y == 0 and 99 < x < 1000

for x in range(999_999, 10_000, -1):
  if ispalindrome(x) and d3(x):
    print(x)
    break