Home » 오일러 프로젝트 32

오일러 프로젝트 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에 대한 집합을 만들어서 중복을 자동으로 걸러주는 쪽이 좋다. (중복을 제외하는 경우에 있어서는 리스트에 대해서 중복검사(이다.)를 하는 것보다 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. 곱셈의 결과의 범위를 한정한다. 곱셈의 결과가 기대한 자리수를 넘어서는 경우에는 그 이후로 더 큰값만 나올테니 빨리 루프를 빠져나온다.
  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, +))
}
0 Comments

No Comment.