프로젝트 오일러 51

Swift 풀이

분량상, 소수 검사 함수나 순열 생성함수는 생략한다.

패턴으로부터 숫자 목록을 생성하는 함수

패턴은 [Bool] 타입이며, 여기에 n 자리 정수를 받아서 치환되는 숫자 목록을 생성하는 함수를 작성해보자.

  1. 패턴의 끝자리가 치환숫자 자리인 경우는 8개의 소수를 만들 수 없으므로 아예 빈 배열을 리턴한다.
  2. 주어진 숫자의 1자리 수가 끝에 오는 경우에도 짝수 혹은 5의 배수이면 미리 빈 배열을 리턴한다.

이 함수가 실질적으로는 상당히 많이 호출될 것이기 때문에1 여기서 이렇게 보초를 세워서 가능한 성능을 높여본다.  참고로 true 인 경우에는 치환숫자를 false 인 경우에는 고정 숫자에서 하나를 채운다.

func makeNumbers(pattern: [Bool], with n: Int) -> [Int] {
  // 주어진 정수를 고정숫자의 배열로 전환한다.
  let fixedNumbers:[Int] = {
    let c = Int(log10(Double(n)))
    return (0...c).map{ n / Int(pow(10, Double(c-$0))) % 10 }
  }()
  var temp:[Int] = [] // 결과 배열
  // 보초. 우선 맨끝자리가 치환자리면 실패
  if let last = pattern.last, last { return [] }
  // 정수값 1자리가 0,2,4,5,6,8이 아니어야 한다.
  if [0,2,4,5,6,8].contains(n % 10) { return [] }

  // 숫자를 만드는 구간
  for a in (pattern[0] ? 1...9 : 0...9) { // 첫자리가 치환영역이면 0은 올 수 없다.
    var (x, g) = (0, fixedNumbers.makeIterator())
    for b in pattern {
      x = x * 10 + (b ? a : g.next()!)
    }
    temp.append(x)
  }
  return temp
}

다음은 특정 자리수 구간을 검사하는 함수를 작성한다. 역시 별로 어려울 것 없다.

func test(_ n: Int) -> Bool {
  let lowerBound = Int(pow(10, Double(n-4)))
  let upperBound = lowerBound * 10
  var template = Array(repeating: false, count: n)
  (0..<3).forEach{ template[$0] = true }
  for k in lowerBound..<upperBound {
    for i in (0..<(factorial(n))) { // 템플릿 순열을 모두 검사
      let pattern = permutation(pattern, i)
      let numbers = makeNumbers(pattern: pattern, with: k)
      if !numbers.isEmpty && numbers.filter(isPrime).count == 8 {
        print(numbers.min()!)
        return true
      }
  }
  return false
}   

최종 결과

 


  1. 네자리수부터 체크하는 경우 답을 찾을 때까지 106,827회 호출된다.