오일러 프로젝트 36

오일러 프로젝트 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)