프로젝트 오일러 #4: 가장 큰 회문 곱

링크: Project Euler , HackerRank

문제 설명:

두 개의 3자리 숫자를 곱하여 만든 가장 큰 회문을 찾아야 하고, HackerRank의 경우 상황은 비슷하지만 크기가 작은 가장 큰 회문을 찾아야 합니다.

NNN

.

해결책:

회문(palindrome)은 다음과 같이 두 가지 방법으로 같은 숫자를 읽습니다.

121121121

오른쪽에서 왼쪽(정상)과 왼쪽에서 오른쪽(역방향)의 두 가지 방식이 동일합니다.

따라서 숫자가 회문인지 여부를 감지하기 위해 숫자가 역수와 같은지 여부를 확인할 수 있습니다. 그렇다면 회문이고 그렇지 않으면 그렇지 않습니다. 숫자를 반전시키려면 숫자의 마지막 숫자를 팝하고 반복적으로 새 숫자의 첫 번째 숫자(역숫자가 됨)로 푸시할 수 있습니다.

def is_palindrome(x: int) -> bool:
    """
    Checks if the given number is a palindrome or not.
    """
    x1 = x
    rev = 0
    while x1 != 0:
        rev *= 10
        rev += rev % 10
        x1 //= 10

    return rev == x

이제 HackerRank 문제의 경우 가능한 모든 회문을 미리 계산하고 초기에 정렬하는 것이 더 쉬울 것입니다. 3자리 숫자의 모든 제품을 생성하고 제품이 회문인 경우 회문 목록에 추가할 수 있습니다.

def _calculate_palindromes(self):
    palindromes = []
    for three_digit_number_a in range(100, 1000):
        for three_digit_number_b in range(three_digit_number_a, 1000):
            product = three_digit_number_a * three_digit_number_b
            if is_palindrome(product):
                palindromes.append(product)

    self._palindromes = sorted(palindromes, reverse=True)

아래에서 가장 큰 회문을 찾으려면

NNN

, 미리 계산되고 정렬된 회문을 반복하고 다음보다 작은 첫 번째 회문을 반환할 수 있습니다.

NNN

.

def below(self, n: int) -> int:
    """Returns largest palindrome less than or equal to n"""

    for palidrome in self._palindromes:
        if palidrome < n:
            return palidrome

    return None

최종 Hackerrank 코드는 다음과 같습니다.

#!/bin/python3

import sys

def is_palidrome(n: int) -> bool:
    n1 = n
    rev = 0
    while n1 != 0:
        rev *= 10
        rev += n1 % 10
        n1 //= 10
    return rev == n


class PalidromeHelper:
    """
    Precalculates all possible palindromes generated by-product of 3-digit numbers.
    """

    _palindromes = []

    def __init__(self):
        self._calculate_palindromes()

    def _calculate_palindromes(self):
        palindromes = []
        for three_digit_number_a in range(100, 1000):
            for three_digit_number_b in range(three_digit_number_a, 1000):
                product = three_digit_number_a * three_digit_number_b
                if is_palidrome(product):
                    palindromes.append(product)

        self._palindromes = sorted(palindromes, reverse=True)

    def below(self, n: int) -> int:
        """Returns largest palidrome less than n"""

        for palidrome in self._palindromes:
            if palidrome < n:
                return palidrome

        return None

helper = PalidromeHelper()
t = int(input().strip())
for a0 in range(t):
    n = int(input().strip())
    print(helper.below(n))

ProjectEuler 문제의 경우 가능한 가장 큰 회문을 찾아야 하므로 이 경우 math.inf 메서드에 below를 전달할 수 있습니다.

if __name__ == "__main__":
    helper = PalidromeHelper()
    print(helper.below(math.inf))

읽어 주셔서 감사합니다.