오일러 프로젝트 52

이번 문제는 순열관계에 있는 수에 대한 문제이다.

125874를 2배하면 251748이 되는데, 이 둘은 같은 숫자로 이루어져 있고, 순서만 다릅니다. 2배, 3배, 4배, 5배, 6배의 결과도 같은 숫자로 이루어지는 가장 작은 수는 무엇입니까?

접근

순열관계의 수는 두 수를 구성하고 있는 숫자들이 자리수의 위치만 다르고 모두 같은 구성을 이루고 있다. 숫자 x, y, z 로 이루어진 세 자리 수 xyz 와 zxy 의 차이를 살펴보자. x, y, z는 사실 한자리 자연수이므로 각 수는 다음과 같이 구성된다.

"xyz" = 100 * x + 10 * y + z
"zxy" = 100 * z + 10 * x + y

이 둘의 차이를 계산하면 모두 의 값끼리 더한 값이 되므로 9의 배수가 된다. 즉 “순열 관계”의 두 수의 차는 항상 9의 배수이다. 그런데 어떤 수 N을 2배 했을 때 순열이 된다는 것은 N 자체가 9의 배수라는 의미이다. 또한 6배 할 때까지 순열이 유지된다는 것은 해당 값이 6자리라는 의미이기도 하다. 따라서 6자리 9의배수 중에서 답을 찾으면 된다.

순열

두 숫자가 순열이라는 것은 어떻게 알 수 있을까? 두 수를 이루는 숫자의 집합을 정렬해서 비교해보면 된다. 따라서 최종 풀이는 다음과 같다.

def p053():
  def test(n):
    s = sorted(str(n))
    for i in range(2, 7):
      if s != sorted(str(n * i)):
        return False
    return True
  for x in range(99999,999999,9):
    if test(x):
      print(x)
      return
%time p053()

참고로 이 숫자는 문제에 나온 수와 순열이다.

보너스 : Swift 풀이

동일한 알고리듬이다. 문자열로 변환해서 정리하는 것은 Swift에서는 비싼 작업이라, 로그값을 이용해서 자리 수를 나눴다.

import Foundation
main: do {
  let tidyup:(Int) -> [Int] = { n in
    let c = Int(log10(Double(n)))
    return (0...c).map{ n / Int(pow(10, Double($0))) % 10 }.sorted()
  }
  let test: (Int) -> Bool = { n in
    let s = tidyup(n)
    for i in 2...6 {
      if s != tidyup(n * i) { return false }
    }
    return true
  }
  for x in stride(from:99_999, to:999_999, by:9) where test(x) {
    print(x)
    break
  }
}