펜디지털 숫자에 관한 문제. 두 개의 수를 곱하는 곱셈식의 숫자들을 연결하였을 대 팬디지털 숫자를 만들 수 있는 경우들을 찾는 작업이다.
1부터 n까지의 각 숫자를 한번씩만 써서 만들 수 있는 숫자를 팬디지털(pandigital)이라고 합니다. 예를 들면 15234는 1부터 5의 숫자가 한번씩만 쓰였으므로 1 ~ 5 팬디지털입니다. 7254라는 숫자는 그런 면에서 특이한데, 39 × 186 = 7254 라는 곱셈식을 만들 때 이것이 1 ~ 9 팬디지털이 되기 때문입니다. 이런 식으로 a × b = c 가 1 ~ 9 팬디지털이 되는 모든 c의 합은 얼마입니까? (참고: 어떤 c는 두 개 이상의 (a, b)쌍에 대응될 수도 있는데, 이런 경우는 하나로 칩니다)
http://euler.synap.co.kr/prob_detail.php?id=32
접근
팬디지털 수는 1~n 까지의 숫자가 하나씩만 있는 숫자이다. 따라서 숫자를 문자열로 변환하고 1~n의 각 숫자에 대해 모든 숫자가 하나씩 있는지를 검사해볼 수 있겠다. 하지만 보다 간단한 방법은 문자열로 변환한 값을 정렬하고 다시 이어붙인 “정렬된 문자열”이 “12345789”가 되는지 살펴보는 것으로 간단히 처리할 수 있다. 이렇게 두 수 a, b로 그 곱인 c를 구하고, a,b,c를 이어붙인 숫자가 팬디지털이 되는지를 검사한다.
곱셈식이 팬디지털이 되려면 2자리 * 3자리 = 4자리가 되거나, 1자리 * 4자리 = 4자리가 되는 경우만 살펴보면 된다. 그외의 경우에는 전체 숫자를 9개로 만들 수 있는 경우가 없다. 참고로 다른 두 수를 곱해서 팬디지털 곱셈식을 만들 때 결과 c가 동일하다면 1건으로 치기 때문에 c에 대한 집합을 만들어서 중복을 자동으로 걸러주는 쪽이 좋다. (중복을 제외하는 경우에 있어서는 리스트에 대해서 중복검사(
set 타입을 이용하는 편이 훨씬 성능이 좋은 경우가 많다. (
def check_pandigital(a, b):
c = a * b
d = "%d%d%d" % (a, b, c)
return "".join(sorted(d)) == "123456789"
def e32():
s = set()
for a in range(1,10):
for b in range(1234,9999):
if check_pandigital(a, b):
s.add(a*b)
for a in range(12, 100):
for b in range(123,1000):
if check_pandigital(a, b):
s.add(a*b)
print(sum(s))
%time e32()Swift 풀이
Swift에서도 방법은 대동소이하다. 문제는 Swift의 문자열을 이용한 조작은 현재까지는 제법 무겁고 성능이 안 따라온다는 사실. 따라서 튜닝을 위해 몇 가지 보초를 세운다.
- 곱셈의 결과의 범위를 한정한다. 곱셈의 결과가 기대한 자리수를 넘어서는 경우에는 그 이후로 더 큰값만 나올테니 빨리 루프를 빠져나온다.
- 팬디지털 검사에서도 글자 자리수를 먼저 계산해본다. (너무 작은 수는 여기서 미리 탈락)
이렇게해서 가뿐하게 1초 이내에 안착할 수 있다.
func test(_ a:Int, _ b:Int) -> Bool {
let s = "\(a)\(b)\(a*b)"
guard s.count == 9 else { return false }
let p = s.characters.sorted()
return String(p) == "123456789"
}
main: do {
var r = Set<Int>()
for a in 1...9 {
for b in 1234...9876 {
if a * b > 9999 { break }
if test(a, b) { r.insert(a*b) }
}
}
for a in 12...98 {
for b in 1234...9876 {
if a * b > 9999 { break }
if test(a, b) { r.insert(a*b) }
}
}
print(r.reduce(0, +))
}