태그: 오일러프로젝트

오일러 프로젝트 38 번 문제는 반복된 곱셈의 결과를 이어 붙인 것이 1-9 팬디지털 숫자를 만들어 내는지를 보고, 그렇게 만들어지는 팬디지털 숫자중에 가장 큰 값을 찾는다. 문제 그대로를 코딩하면 되는 것이기도 하고 검사 범위도 매우 좁기 때문에 1도 어렵지 않은 문제이다.

숫자 192에 1, 2, 3을 각각 곱합니다.

92 × 1 = 192
192 × 2 = 384
192 × 3 = 576

곱한 결과를 모두 이어보면 192384576 이고, 이것은 1 ~ 9 팬디지털(pandigital)인 숫자입니다. 이런 과정을 편의상 ‘곱해서 이어붙이기’라고 부르기로 합니다. 같은 식으로 9와 (1, 2, 3, 4, 5)를 곱해서 이어붙이면 918273645 라는 1 ~ 9 팬디지털 숫자를 얻습니다. 어떤 정수와 (1, 2, … , n)을 곱해서 이어붙였을 때 얻을 수 있는 가장 큰 아홉자리의 1 ~ 9 팬디지털 숫자는 무엇입니까? (단 n > 1) (http://euler.synap.co.kr/prob_detail.php?id=38)

 

접근

어떤 수 N에 대해서 1부터 9사이의 값 i (1, 2, 3 .. 9) 와 곱한 결과들을 모아서 팬디지털이 되는지 검사한다. 즉 문제의 내용 그대로를 코딩하면 된다.

1. 임의의 수 n에 대해서
2. 1, 2, 3..을 차례로 곱해나가면서, 곱한 값을 연결한다.
3. 2의 과정을 반복하다가 결과가 9자리 이상이 되면 1-9 팬디지털인지 검사한다.

참고로 범위는 어떻게 정할까? 6자리의 경우 1, 2를 곱해서 붙이면 기본 12자리가 되므로 실패. 따라서 5자리 범위까지만 테스트한 후 최대값을 찾으면 되겠다.

def test(n):
    s = ""
    for i in range(1, 10):
        s += str(i * n)
        if len(s) >= 9:
            break
    if "".join(sorted(s)) == "123456789":
        return s
    return None

def e038():
    print(max(test(x) for x in range(1, 100_000) if test(x)))

%time e038()

Swift 풀이

동일한 알고리듬이다. 사실 펜디지털 숫자를 만들 수 있냐 없냐를 가지고 파이썬의 test 함수가 문자열 혹은 None 을 리턴했는데, 이는 옵셔널을 리턴하는 함수의 컨셉과 일치한다. 그리고 이렇게 이어진 결과에서 non-nil인 결과만을 추려내고 싶다면 flatMap을 쓰는 것이 가장 간편하다.

// Swift 4.0
func test(_ n: Int) -> String {
  var s = ""
  for i in 1...9 {
    s += "\(n * i)"
    if s.count >= 9 { break }
  }

  // 문자열을 정렬하는 것은 유니코드 문자배열을 정렬한 것이므로 [Chracter] 타입이 된다. 
  // 따라서 이는 Characater의 시퀀스이므로 String으로 바로 만들 수 있다.
  if String(s.sorted()) == "123456789" { return s } 
  return nil
}

print((1...99999).flatMap(test).max()!)