오일러 프로젝트 32

펜디지털 숫자에 관한 문제. 두 개의 수를 곱하는 곱셈식의 숫자들을 연결하였을 대 팬디지털 숫자를 만들 수 있는 경우들을 찾는 작업이다.

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에 대한 집합을 만들어서 중복을 자동으로 걸러주는 쪽이 좋다. (중복을 제외하는 경우에 있어서는 리스트에 대해서 중복검사(O_{(n)}이다.)를 하는 것보다 set 타입을 이용하는 편이 훨씬 성능이 좋은 경우가 많다. (O_1이다.)

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. 곱셈의 결과의 범위를 한정한다. 곱셈의 결과가 기대한 자리수를 넘어서는 경우에는 그 이후로 더 큰값만 나올테니 빨리 루프를 빠져나온다.
  2. 팬디지털 검사에서도 글자 자리수를 먼저 계산해본다. (너무 작은 수는 여기서 미리 탈락)

이렇게해서 가뿐하게 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, +))
}