프로그래밍 공부를 위해 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