4. Largest palindrome product

projecteuler.net/problem=4

Problem 4 - Project Euler

 

 

문제는 다음과 같습니다.

A palindromic number reads the same both ways. The largest palindrome made from the product of two 2-digit numbers is 9009 = 91 × 99.

Find the largest palindrome made from the product of two 3-digit numbers.

 

두 개의 세자리수의 곱으로 나타내어지는 가장 큰 palindromic number를 구하는 문제입니다.

palindromic이란 회문(回文)으로, "앞에서부터 읽으나 뒤에서부터 읽으나 동일한 단어나 구"를 의미합니다. 그러므로palindromic number란, 123321, 231132, ... 와 같은 숫자들입니다.

이번 문제 또한, brute force방식으로 풀었었습니다.

 

풀이 과정은 다음과 같습니다.

1. 확인할 숫자를 문자열로 변환합니다.

2. 문자열로 변환한 숫자를 palindromic number인지 확인합니다.

  2-1. palindromic number일 경우 세자리수의 곱으로 나타내어지는지를 확인합니다.

  2-2. palindromic number가 아닐경우 확인할 숫자를 1 감소시킵니다.

3. 2-1을 만족하는 숫자가 나타날 경우, 해당 숫자를 출력합니다.

 

처음 입력으로 들어갈 숫자는 가장 큰 세 자리 수의 곱인 999 * 999 = 998001입니다.

 

코드는 아래와 같습니다.

 

# num : 999 * 999 = 998001
# res : largest palindromic product
# isThreePaliNum : check num is palindrome made from the product of two 3-digit
num=998001
res = 0
isThreePaliNum = False

while isThreePaliNum != True :
    NStr=str(num)
    for i in range(0, 3) :
        # if first digit and last digit is not same
        if NStr[i] != NStr[5-i] :
            break
        # if num is palindromic number
        if i==2 :
            DNum=999
            # find numbers what product of two 3-digit is num
            while DNum!=99 :
                a, b = divmod(num, DNum)
                # if divisor is 3-digit and remainder is zero
                if len(str(a))==3 and b == 0 :
                    res = num
                    isThreePaliNum=True
                    break
                        
                DNum-=1
    num-=1
    

print(res)

 

 

아래의 블로그에서는 두 가지 방식을 제시하고있습니다.

www.mathblog.dk/project-euler-problem-4/

Solution to Project Euler problem 3 in C# | MathBlog

 

1. 두개의 세자리수의 곱을 구한 후, 해당 숫자가 palinpalindrome number인지 확인한다.

2. palindrome number를 구한 후, 해당 숫자가 두개의 세자리수의 곱으로 나타낼 수 있는지를 확인한다.

 

해당 블로그에서는 2번의 방법을 이용한 코드만 게재하였습니다.

저의 코드와 다른 점은, palindrome number를 입력받은 숫자를 1씩 빼면서 체크하는 것이 아닌, 구하는 함수를 따로 작성하였다는 점입니다.

 

이런 점을 보면, 예전의 자신이 얼마나 이상하게 코드를 짯는가를 다시 한번 느끼는 바입니다.. 그래도 예전 것을 하시 복기하고, 더욱 나아질 점은 없는지 확인하면서 성장하는것 아니겠습니까..