오일러 프로젝트 36 번은 대칭수에 대한 문제이다. 대칭수는 이전에도 몇 번 나왔던 문제이다.
대칭수(palindrome)인 585는 2진수로 나타내도 10010010012가 되어 여전히 대칭수입니다. 10진법과 2진법으로 모두 대칭수인 1,000,000 이하 숫자의 합을 구하세요. (주의: 첫번째 자리가 0이면 대칭수가 아님)
http://euler.synap.co.kr/prob_detail.php?id=36
접근
10진수값과 2진수값이 모두 대칭수인 수를 1백만 이하에서 찾는다. 2진수의 경우 짝수라면 맨 끝자리 수가 0이 되므로 대칭수가 될 수 없다. 따라서 모든 검사 대상은 “홀수”로 좁혀진다.
파이썬에서 회문검사를 가장 빠르게 할 수 있는 방법은 s == s[::-1] 이라고 했다. 그리고 10진수를 2진수로 바꾸는 것은 bin() 내장함수를 사용할 수 있다. 대신에 bin() 함수는 0b 라는 이진수 리터럴을 위한 접두어를 붙이기 때문에 앞의 두 글자를 떼어주어야 한다.
이 두 가지 규칙을 이용해서 간단하고 빠르게 문제를 풀 수 있다.
def is_palindrome(n):
s = str(n)
return s == s[::-1]
def test(n):
return is_palindrome(n) and bin(n)[2:] == bin(n)[2:][::-1]
def e36():
r = sum((x for x in range(1, 1000000, 2) if test(x)))
print(r)
%time e36()
# Wall time: 549보너스 : Swift 풀이
Swift에서 문자열로 대칭수를 판별하려고하면 성능이 급격히 하락한다. 그나마 성능을 높일 수 있는 방법은 “각 자리수에 맞게 숫자를 떼어내어, 정수배열로 만들고 이를 뒤집어서 원본과 비교한다”이다. 그리고 Array.reversed() 마저도 시작위치와 끝위치로부터 한칸씩 움직이며 값을 비교하는 “완전 고전적인 체크”의 성능이 미약하게나마 더 좋다.
그래서 다음과 같이 코딩하니까, 가까스로 1초이내로 답을 찍더라.
func test(_ n: Int) -> Bool {
// 10진수일 때 먼저 체크
var a = n
var b = n
var tempA = Array<Int>()
var tempB = Array<Int>()
while a > 0 {
tempA.append( a % 10 )
a /= 10
}
for i in 0..<tempA.count/2 {
if tempA[i] != tempA[tempA.count - i - 1] { return false }
}
// 2진수일 때 체크. 로직은 똑/같/다
while b > 0 {
tempB.append(b%2)
b /= 2
}
for i in 0..<tempB.count/2 {
if tempB[i] != tempB[tempB.count - i - 1] {return false }
}
return true
}
var s = 0
for i in stride(from: 1, through: 100_0000, by: 2) {
if test(i) { s += i }
}
print(s)