오일러 프로젝트 62

오일러 프로젝트 62 번 문제는 순열로 이루어진 숫자들 사이에서 세 제곱수가 5번 나오는 수를 찾는 것이다.  60번을 넘어서면서부터는 한국어 사이트의 포럼에서 정답자 수나 코드를 올린 포스트의 수가 격감하는데, 이 문제는 그리 어려운 수준의 문제는 아니다.

세제곱수인 41063625(=345^3)로 순열을 만들어 보면 그 중에서 56623104(=384^3)와 66430125(=405^3)가 또 세제곱수입니다. 실제 41063625는 자릿수로 만든 순열 중에서 3개가 세제곱수인 가장 작은 수입니다.
그러면 자릿수로 만든 순열 중에서 5개가 세제곱수인 가장 작은 숫자는 무엇입니까?

접근

특정한 그룹(세제곱수들)에서 순열을 만들었을 때 세제곱수가 5번 나올 수 있는, 즉 네 번 더 나올 수 있는 집합을 찾는 것이다. 여기서는 순열보다는 세제곱수 자체를 생각해보자. 왜냐면 특정 한계값 내에서 세제곱수가 가장 개수가 적을 것이기 때문이다.
따라서 한 자리 수의 세 제곱수들을 같은 순열에 포함되는 것끼리 묶어서 정리한다. 그 중에서 답이 있는지를 찾아보고 없으면 다음 두 자리 수의 세 제곱수에 대해서 같은 테스트를 해나가면서 찾아본다.  답은 순식간에 찾아진다.

def find(n): 
  ## n자리 수의 세제곱수에서 같은 순열인 것들을 묶어보자
  xs = [x**3 for x in range(10**(n-1), 10**n)]
  memo = dict()
  for x in xs:
    t = tuple(sorted(str(x)))
    memo.setdefault(t, []).append(x)
    if len(memo[t]) == 5:
      return memo[t][0]
  return None
def main():
  t = 1
  while True:
    r = find(t):
    if r is not None:
      print(r)
      break
    t += 1
%time main()
## Wall time: 41ms

Swift 풀이

파이썬과 달리 튜플을 사전의 키로 쓸 수 없다는 약점이 있다. 그런데 순열은 “숫자를 정렬한 결과”를 보기 때문에 사실 원소들의 순서는 상관이 없다. Swift에서는 Set 타입이 그 자체로 다시 Hashable이라는 특징이 있다. 이를 응용한다. 또한 정수와 문자열을 오가는 변환이 성능상 그리 유리하지 않기 때문에 로그를 이용해서 숫자들을 분리하도록 했다.

func makeKey(_ n: Int) -> Set<Int> {
  let c = Int(log10(Double(n)))
  return Set((0...c).map{ n / Int(pow(10, Double($0))) % 10 }
}
func find(_ level: Int) -> Int? {
  guard level > 0 else { return nil }
  let range = (Int(pow(10, Double(level-1)))..<Int(pow(10, Double(level))))
  var memo = [Set<Int>: [Int]]()
  for x in (range.map{ $0*$0*$0 }) {
    let key = makeKey(x)
    if memo[key] == nil { memo[key] = [] }
    memo[key]?.append(x)
    if memo[key]!.count == 5 { return memo[key].first }
  }
  return nil
}
do { // 대략 10ms 내외
  var l = 1
  while true {
    if let x = find(l) {
      print(x); break
    }
    l += 1
  }
}