프로젝트 오일러 4번

4번 

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.

palindrome 은 우리말로 회문이다. 풀어말하자면 앞으로 읽으나 뒤로 읽으나 같은 것을 말한다.

ex ) 토마토, 12321

3-digit number는 세 자리수.

즉 문제에서는 두 3자리 수의 (계산)결과물 중 가장 큰 회문을 찾으라는 것이 된다.

가장 큰 수를 찾아야하니 당연히 곱셈부터 찾아봐야한다.  999부터 역순으로.

for문을 쓰는건 쉬우니 회문체크를 먼저 만들어보자.

회문을 어떻게 판별할까? 나는 수의 길이를 이용하기로 했다. 

수의 길이(N)가 짝수라면 앞에서 N/2번, 뒤에서 N/2번 확인하여 같은 수면 된다.

수의 길이(N)가 홀수라면 앞에서 N+1/2번, 뒤에서 N+1/2번 확인하면 된다. 

 => 홀수인 경우 N = N + 1을 해준다.

그럼 길이는 어떻게 잴까? 

math 모듈의 log10을 이용하면 10진수의 자리수를 셀 수 있다.

1253의 자리수가 알고싶으면 => math.log10(1253) = 3.09795107099415

이 값에 int를 씌운 뒤 1을 더해주면 기대하던 4가 나온다.

 => int(math.log10(num))

리스트 슬라이싱을 사용하여 앞에서 N번, 뒤에서 N번 확인 하면 더 편할 것 같다는 생각이 들어 

각 자리 숫자를 리스트의 원소로 하나씩 넣어 주려 해보았다.

1253을 1, 2, 5, 3으로 표현하기 위해서는 1253 // 1000 % 10, 1253 // 100 % 10, 1253 // 10 % 10, 1253 // 1 % 10

과 같이 표현하면 된다. //는 몫을 구하는 연산자다.

c++로는 아래와 같이 쓸수 있다.

for(int i=1000;i>0;i/=10){

  //do

}

Python으로는 어떻게 쓸까? while문이나 append문을 사용하지 않고

li = [x for x in range(1000, 0, ...)]
#1000
#100
#10
#1

과 같이 리스트를 for문으로 선언하는 깔쌈한 형태로 구현하고 싶어 여러가지 찾아보았다.

range(start, stop[, step])

r[i] = start + step*i

Python Docs에서 찾은 정보다. 위와 같은 형식이라면 range를 바꿔서는 원하는 결론에 도달할 수 없을 것 같다.

고민 끝에 Stackoverflow에 질문 글을 올렸다. 

https://stackoverflow.com/questions/54343083/in-python-range1-100-10-doesnt-work

영작 실력은 부족하지만 10분만에 6개의 답변이나 달렸다. 대단한 곳이다.

답변에서 힌트를 얻어 수를 리스트로 변환해주는 코드를 완성했다.

li = [num//(10 ** x)%10 for x in range(int(math.log10(num)), -1, -1)]

그리고, 구글링을 토대로 만든 더 편한 방법이다. 

li = [int (i) for i in str(num)]

정말 뚝딱 만들었다.

더 편한 방법이 있을거라 생각했고,, 나의 생각을 먼저 구현해보고 싶다는 생각에 구현한 것이므로 얻어간게 있다고 생각한다.

아무튼 리스트로 변환한 덕분에, li에 들어간 수가 회문인지 판단하기 위한 코드는 아주 간단해졌다.

li == li[::-1]

li[::-1]은 리스트를 거꾸로 만들어준다.

따라서 반환 값이 True라면 회문이다.

완성된 함수 형태

def is_pail(num):
     li = [num//(10 ** x)%10 for x in range(int(math.log10(num)), -1, -1)]
     return li == li[::-1]

이제 for문을 구성하기만하면 문제는 끝이다.

범위는 999~100인 이중 반복문. 다음과 같이 구현했다.

for i in range(999, 99, -1):
      for j in range(999, 99, -1):
         if(is_pail(i*j)):
            print(i*j)
return #exit()

첫 결과값은 580085. 하지만 이내 잘못된 알고리즘임을 알았다. 

i가 999인 동안 j는 100까지 떨어지고 이는 당연히 998 * 999보다 작기에 첫 결과값이 가장 큰 값임을 보장할 수 없게 되는 것이다.

다음은 수정한 코드의 나쁜 예다. 바로 생각나는게 없어 한번 구현해봤다.

ans = []
   for i in range(999, 99, -1):
      for j in range(999, 99, -1):
         if(is_pail(i*j)):
            ans.append(i*j)
   print(max(ans))

위의 코드는 3.9 초 정도 걸린다.

정답을 구할 수는 있지만 아주 느리고 파이썬과 어울리지 않고 마음에 들지도 않는 코드다.

어떻게하면 가장 큰 값을 보장 해줄 수 있을까? 

단위를 정해서 999*999 ~ 999*989 , 998*999 ~ 998*989이런식으로 끊어서 계산하는 것은 어떨까? 

우선 단위를 33으로 잡고 코드를 짜봤다.

for i in range(999, 99, -1):
      for j in range(999, 99, -1):
         for k in range(33):
            if(is_pail(j * (i - k))):
               print(j * (i - k))
               return;

걸린시간은 0.04초 가량. 하지만 답이 886688, 오답이다. 짜면서 느낀거지만 이 방법의 문제는 오차가 발생한다는 것이다. 

처음엔 두 수가 33차이 나는 곱셈 값까지만 구할 수 있다고 생각했으나 j 값이 줄어드는 것과 k는 독립시행이므로 33보다는 큰 차이까지 구

할 수 있다. 실제로 33일 때의 두 수는 916 968 이다.

단위를 111로 잡으니 답이 나왔다.

for i in range(999, 99, -1):
      for j in range(999, 99, -1):
         for k in range(111):
            if(is_pail(j * (i - k))):
               print(j * (i - k))
               return;

하지만 이 방법은 예측할 수 없는 오차가 발생한다. 사용할 수 없다.

이쯤하고 프로젝트 오일러에서 문제를 푼 선배들의 코드를 배우러 가자마자 욕이 절로 나오는 엄청난 코드를 발견했다.

한줄짜리 코드가 말이되나? 따봉을 주고 긁어왔다.

print(max([x*y for x in range(100, 1000) for y in range(100, 1000) if str(x*y) == str(x*y)[::-1]]))

당연한가 싶지만 정답이었고 걸린 시간은 0.95초. 적어도 내 3.9초짜리 코드보다는 4배정도나 빠른셈이다.

파이썬 공부를 헛한건 아닌가보다. 보자마자 이해가 되었다.

내 코드와 다른점이라하면.. 나는 list의 append기능으로 하나씩 넣은다음 max를 구했고

이 코드는 list선언문 내에서 한번에 처리했다. 또 str(x*y)로 다른 함수를 만들지 않고 사용하였다.

그렇다면 둘 중에 무엇이 얼마나 성능에 영향을 끼친 걸까?

list = []

for x in range(100, 1000):
    for y in range(100, 1000):
        z = x * y
        if str(z) == str(z)[::-1]:
            list.append(z)

print(max(list))

이 코드의 실행시간은 0.88초. 내 코드와 회문 확인 부분만 다르다.

append라 더 느릴 줄알았지만 신기하게도 위의 코드보다 빠르다.

실행시간이 소수점 두자리까지는 거의 바뀌지 않기 때문에 다시 실행해봐도 더 빠르다.

깃허브 코드

https://github.com/shining-stone/Codeing-Problem-solution/blob/master/Projecteuler/4.py