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

프로그래밍 공부를 위해 Projetct Euler의 문제 풀이를 연습하는 내용입니다.
문제(problem), 제 답변(answer), 추천하는 타인 답변(solution)으로 구성되어 있습니다.
기본적으로 풀이는 R을 사용하였지만, 일부 연습을 위해 Python으로도 구현해 보았습니다.

Problem

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

Answer & Solution - R

• 어떤 수(n)에 대하여 대칭수인지 판단하는 함수(is_palin) 작성

  • 텍스트 처리 패키지(stringr)를 이용하여 어떤 수(n)의 중간 자리수를 찾고(nchar(n))/2) 비교

• 세자리 수의 곱 비교를 위해 증가시키는 수의 범위(100:999) 한정

• code : R 코드

# Answer

# install.packages("stringr")
library(stringr)
ptm <- proc.time()

is_palin <- function(n){
  length = as.integer(nchar(n))/2
  for(i in 1:length){
    if(str_sub(as.character(n), i, i) != str_sub(as.character(n), nchar(n)+1-i, nchar(n)+1-i)){
      return(0)
    }
  }
  return(1)
}

result = 0
for (i in 100:999){
  for (j in 100:999){

    mul = i * j
    if (is_palin(mul) == 1){

      result = max(mul, result)
    }
  }
}
print(result)
print(proc.time() - ptm)
# 906609

# 사용자  시스템 elapsed 
# 16.28    0.10   16.55 

• 결과는 동일하게 나타났으나 아래 코드의 처리 속도가 약 183배 빠르게 나타남 (python 해법을 R로 재구현 함)
  • 함수 목적 : is_palin은 어떤 수(n)가 대칭수인지 판단하는 것이 목적이라면, 솔루션의 palindrome은 대칭수를 만드는 것 이 목적임
  • 큰 수를 구하는 문제이기에 작은 수부터 증가시키는 것보다 큰 수에서 감소시키면서 답을 찾는 것이 팁
  • 6자리 중 가장 큰 수 부터 감소시키면서 나머지 비교

# Solution

library(stringi)
ptm <- proc.time()

palindrome <- function(num){

  var = as.character(num)
  mrr_var = stri_reverse(var)

  # print(var)
  # print(mrr_var)
  return(as.integer(paste(var,mrr_var,sep = "")))
}

# digit <- readline('몇 자리 대칭수를 원하십니까?(짝수를 입력하세요) : ')
digit <- 6

half_digit <- as.integer(digit) /2 

cnt = 0

for (j in seq(10^half_digit-1, 10^(half_digit-1), -1)){

  pal = palindrome(j)

  for (i in j:10^half_digit){
    # %% : 나눗셈 후 나머지 반환
    if(pal %% i == 0 ){
      # %/% : 나눗셈 후 몫 반환
      if(pal %/% i < 10^half_digit){

        # sprintf("%d = %d x %d", pal, i, pal%/%i)
        cat(pal, "\t= ", i, "\t x ", pal%/%i, "\n")
        cnt = cnt + 1
      }
      break
    }
    if(cnt == 1){
      break
    }
  }
}

print(proc.time() - ptm)
# 906609  =  913  x  993

#  사용자  시스템 elapsed 
#  0.05    0.04    0.09 

Answer & Solution - Python

• code : Python

# Answer

import time

start = time.time()
def is_palin(n):
    length = int(len(str(n))/2)
    for i in range(0, length):
        if str(n)[i] != str(n)[-i-1]:
            return 0
        else:
            pass
    return 1

result = 0
for i in range(100, 999):

    for j in range(100, 999):

        mul = i * j

        if is_palin(mul) == 1:

            result = max(mul, result)

print("result : ", result)
elasped = time.time() - start

print(f'{elasped} sec elasped!.')
# 1.5578441619873047 sec elasped!.

• 제안 답과 유사하게 풀었으나 대칭수 판단로직이 다르며 처리속도도 50%가량 감소함
  • 대칭수 판단 : i와 j의 곱으로 만들어진 mul을 텍스트 변환 후(sMul), 역순(rMul)과 비교

# Solution-1

start = time.time()
maxValue = []
for i in range(1, 1000):
    for j in range(1, 1000):
        mul = i * j
        sMul = str(mul)
        rMul = sMul[::-1]  # sMul 값 역순 출력

        if sMul == rMul:
            maxValue.append(mul)
max(maxValue)

elasped = time.time() - start

print(f'{elasped} sec elasped!.')
# 0.7109289169311523 sec elasped!.

• 상단의 R해법의 원문으로 처리속도가 훨씬 뛰어남

import time

def palindrome(num):
    var = str(num)
    mrr_var = var[::-1]

    return int(var + mrr_var)

digit = int(eval(input('몇 자리 대칭수를 원하십니까?: (짝수를 입력하세요)')))

half_digit = int(digit / 2)

cnt = 0

start = time.time()
for j in range(10 ** (half_digit) - 1, 10 ** (half_digit - 1), -1):
    pal = palindrome(j)
    # print(pal)
    for i in range(j, 10 ** (half_digit)):
        # % : 나눗셈 후 나머지를 반환
        if pal % i == 0:
            # // : 나눗셈 후 몫 반환
            if pal // i < 10 ** (half_digit):

                print(f'{pal} = {i} x {int(pal // i)}')
                cnt += 1
            break
    if cnt == 1:
        break

elasped = time.time() - start

print(f'{elasped} sec elasped!.')
# 0.0009999275207519531 sec elasped!.

System Info.

PyCharm 2019.1 EAP (Community Edition)
Build #PC-191.6014.12, built on March 6, 2019
JRE: 11.0.2+159 amd64
JVM: OpenJDK 64-Bit Server VM by JetBrains s.r.o
Windows 7 6.1
R version 3.5.2 (2018-12-20)
Python 3.6.6
Platform: x86_64-w64-mingw32/x64 (64-bit)
Running under: Windows 7 x64 (build 7601) Service Pack 1
RStudio version 1.1.463