오일러 프로젝트 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~9 팬디지털 곱셈식이 되려면 등장하는 숫자가 9개여야 한다. 이러한 경우는 1자리수 x 4자리수 = 4자리수 가 되거나 2자리수 x 3자리 수 = 4자리수가 되는 케이스만이 존재할 수 있기 때문에 두 개의 구간으로 나눠서 이 부분만 검사하면 범위를 크게 줄일 수 있다. 또 루프를 돌 때 곱셈의 결과가 4자리를 초과하기 시작하면 해당 루프를 빨리 끝내서 시간을 더 단축시킬 수 있다.

펜디지털 곱셈식을 판별하려면 곱셈식의 세 수를 나란히 이어붙인 후 이 수가 팬디지털인지 검사하면 된다. 문자열로 변환한 후 정렬해서 “123456789”와 같은지를 체크하면 된다.

서로 다른 a x b 에 대해서 같은 c를 만드는 팬디지털 곱셈식은 같은 것으로 취급한다고 했기 때문에 결국 팬디지털 곱셈식을 만들 때의 두수의 곱만 set에 기록하여 중복을 제외할 수 있다.

# 1-9 팬디지털 곱셈식 검사
def check(a: int, b: int) -> bool:
  return ''.join(sorted(f"{a}{b}{a*b}")) == "123456789"

%%time
s = set()

# 1 x 4 = 4 케이스
for a in range(1, 10):
  for b in range(1234, 10000):
    if a * b > 9999:
      break
    if test(a, b):
      s.add(a * b)

# 2 x 3 = 4 케이스
for a in range(12, 100):
  for b in range(123, 1000):
    if a * b > 9999:
      break
    if check(a, b):
      s.add(a * b)

print(sum(s))