이번 문제는 순열관계에 있는 수에 대한 문제이다.
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
}
}