파이썬_실전 프로젝트

프로젝트 오일러 4번문제 - 팰린드롬 수

팰린드롬이란 9009나 level 처럼 좌우대칭의 숫자나 문자를 말합니다. 문제는 세자리의 두 정수를 곱해서, 가장 큰 팰린드롬 수를 찾는 문제입니다.

 

Largest palindrome product

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.

 

팰린드롬 확인
if string == string[::-1]

팰린드롬 확인은 위와 같습니다. 문자열 slice 기능인데, 끝에 -1을 넣어주면, 거꾸로 뒤집혀서 출력됩니다. 그래서 두문자열이 같으면 팰린드롬이라고 할수 있겠죠.

 

루프문 구성
for i in range(900,1000):
    for j in range(900,1000):
        print(i*j,end=',')
810000,810900,811800,812700,813600,814500,815400,816300,817200,818100,819000,819900,820800,821700,822600,823500,824400,825300,826200,827100,828000,828900,829800,830700,831600,832500,833400,834300,835200,836100,837000,837900,838800,839700,840600,841500,842400,843300,844200,845100,846000,846900,847800,848700,849600,850500,851400,852300,853200,854100,855000,855900,856800,857700,858600,859500,860400,861300,862200,863100,864000,864900,865800,866700,867600,868500,869400,870300,871200,872100,873000,873900,874800,875700,876600,877500,878400,879300,880200,881100,882000,882900,883800,884700,885600,886500,887400,,,,,,,

루프문을 두개 겹쳐서, 곱셈을 해주면 되고, 가장 큰값을 찾는것이기 때문에, 세자리수중 900번대서부터 시작하면 됩니다.

 

방법1

함수로 분리해도 되고,

def isPalindrome(string):
    if string == string[::-1]:
        return True
    return False

maxValue = 0
for i in range(900,1000):
    for j in range(900,1000):
        product = i*j
        if isPalindrome(str(product)):
            if product>maxValue:
                maxValue = product
print(maxValue)
906609

 

방법 2

함수 없이 해도 되고,

maxValue = 0
for i in range(900,1000):
    for j in range(900,1000):
        product = i*j
        if str(product) == str(product)[::-1]:
            if product>maxValue:
                maxValue = product
print(maxValue)
906609

 

방법 3

결과를 리스트에 저장해도 됩니다.

result = []
for i in range(900,1000):
    for j in range(900,1000):
        product = i*j
        if str(product) == str(product)[::-1]:
            result.append(product)
print(max(result))
906609

 

방법4

아니면 이렇게 풀어도 되네요. itertools 모듈에 combination이라는 함수로 루프문을 만들어주고, 모든수에 대해서 팰린드롬 검사를 한듯 합니다. 그리고 최종값보다 큰수는 palindrome 이라는 변수에 저장해줬구요.

import itertools
palindrome = 0

for n1,n2 in itertools.combinations(range(999,0,-1),2):
    product=n1*n2
    if (str(product) == str(product)[::-1]) and product > palindrome:
        palindrome = product
print (palindrome)
906609

댓글

댓글 본문
  1. Taehee Kim
    이렇게 풀면 더 빠릅니다.

    def palin_fast(number):
    start = number-1
    end = int(number * 0.9)

    for n in range(start,end,-1): # 900이 아니라 999부터 시작합니다.
    for m in range(n,end,-1): # 999* 900이나 900 * 999 나 같기 때문에 모든 경우의 수를 계산할 필요는 없습니다.
    num = n*m
    if str(num) == str(num)[::-1]:
    return(num)

    속도 비교
    palin_fast(100000) # 10만으로 했습니다.
    결과 : 9966006699
    소요 시간 : 0.13867510000000038

    palin_slow(100000)
    결과 : 9966006699
    소요 시간 : 59.55872339999951
버전 관리
nomadlife
현재 버전
선택 버전
graphittie 자세히 보기