오일러 프로젝트 17

오일러 프로젝트 17번 문제. 숫자값을 영어단어로 읽은 후에 해당 단어의 글자수를 세는 작업을 1~1000까지 하며 모든 글자수를 센다. 문제는 이렇다.

1부터 5까지의 숫자를 영어로쓰면 one, two, three, four, five이고 각 단어의 길이를 더하면 3+3+5+4+4+=19이므로 사용된 글자는 모두 19개입니다. 1부터 1,000까지 영어로 썼을 때는 모두 몇 개의 글자를 사용해야 할까요? 빈칸이나 하이픈은 셈에서 제외하면 단어 사이에 and는 셈에 넣습니다. 예를 들어 342를 영어로 쓰면 three hundred and forty-two가 되어서 23글자, 115 = one hundred and fifteen의 경우에는 20글자가 됩니다.

접근

숫자를 단어로 변환하거나, 경우에 따라서는 단어 글자수로 변환하는 함수를 하나 작성할 수 있다.

  1. 1000의 경우에는 one thousand 하나 밖에 없다. (글자수는 11)
  2. 100의 경우에는 (이것이 사실 중요한데) 200의 경우에는 two hundred이다. two hundreds가 아니다.
  3. 100자리를 처리한 후에 나머지가 0이 아니라면 and 가 붙은 후에 10의 자리 이하를 처리한다.
  4. 10의 자리에서 20이상은 하이픈으로 연결되는 두 단어이고, 1~19까지는 한 단어로 되어 있다.

이 경우들만 구분해주면 조금 귀찮을 뿐, 깔끔하게 정리할 수 있다. 다음은 파이썬으로 작성된 words함수로 입력된 정수를 문자열로 변환한다.  1000단위부터 분기를 타면서 진행해도 되고 나머지값을 이용해서 재귀식으로 구성할 수 있는데, 여기서는 재귀식으로 작성해보겠다.

def words(n: int, acc = "") -> str:
  if words == 1000:
    return "onethousand"
  w10= 'twenty thirty forty, fifty, sixty, seventy, eighty, ninety'.split()
  w1 = 'one two three four five six '\
              'seven eight nine ten eleven '\
              'twelve thirteen fourteen fifteen '\
              'sixteen seventeen eighteen nineteen'.split()
  if n is 0:
    return acc
  q, r = divmod(n, 100)
  if q > 0:
    result += w1[q] + 'hundred' + '' if r is 0 else 'and'
  elif 0 < r < 20:
    result += w10[r//10-2]
    r %= 10
  else:
    result += w1[r-1]
    r = 0
  return words(r, acc=result)

print(sum(len(words(x)) for x in range(1, 1001)))

보너스 : Swift 풀이

Swift도 같은 방식으로 처리한다. switch 문을 써서 좀 더 간결하게 작성할 수 있다.

import Foundation

let w1 = "one two three four five six seven eight nine ten eleven twelve thirteen fourteen fifteen sixteen seventeen eighteen nineteen".split(separator: " ")
let w10 = "twenty thirty forty fifty sixty seventy eighty ninety".split(separator: " ")

func read(number n: Int, acc: String="") -> String {
  guard n < 1000 else { return "onethosand" }
  var result = acc
  var (q, r) = (n / 100, n % 100)
  switch (q, r) {
  case (0, 0): return acc // 기저 케이스
  case (0, 1...19): // 19이하 값만 남았을 때
    result += w1[r-1]
    r = 0
  case (0, 20...99): // 20~99 사이 값
    result += w10[r/10-2]
    r %= 10
  case (_, 0): // 100으로 나눠 떨어지는 수
    result += w1[q-1] + "hundred"
  case (_, _): // 100으로 나눠 나머지가 있는 경우, 'and'를 삽입
    result += w1[q-1] + "hundredand"
  }
  return read(number: r, acc: result)
}

print((1...1000).map{ read(number: $0).count }
        .reduce(0, +))

 

  • openingnow

    혹시 if n == 1000 이 부분은 오타인가요?

    • ? 오타없이 실행되는 코드입니다만?