Project Euler. #17. Letters in the numbers

By | 2013/03/10

Project Euler (http://projecteuler.net/) 문제17

If the numbers 1 to 5 are written out in words: one, two, three, four, five, then there are 3 + 3 + 5 + 4 + 4 = 19 letters used in total.

If all the numbers from 1 to 1000 (one thousand) inclusive were written out in words, how many letters would be used?

NOTE: Do not count spaces or hyphens. For example, 342 (three hundred and forty-two) contains 23 letters and 115 (one hundred and fifteen) contains 20 letters. The use of "and" when writing out numbers is in compliance with British usage.

1에서 5까지의 숫자를 글자(영어)로 쓰면 one, two, three, four, five, then there are 3 + 3 + 5 + 4 + 4 = 총 19글자이다.
만약 1에서 1000(one thousand)까지의 숫자를 글자로 쓰면 총 몇개의 글자가 사용되는가?

주의 : 공백이나 하이픈은 세지 않는다. 예를 들어, 342(three hundred and forty-two)는 23글자이고, 115(one hundred and fifteen)는 20글자이다. "and"의 사용은 영국식 영어 표기를 따른 것이다.


fd = {'0':'','1':'one','2':'two','3':'three','4':'four','5':'five','6':'six','7':'seven','8':'eight','9':'nine'}
teens = {'10':'ten','11':'eleven','12':'twelve','13':'thirteen','14':'fourteen','15':'fifteen','16':'sixteen','17':'seventeen','18':'eighteen','19':'nineteen'}
td = {'0':'','2':'twenty','3':'thirty','4':'forty','5':'fifty','6':'sixty','7':'seventy','8':'eighty','9':'ninety'}
hun = {'100':'hundred'}

def checkWords(n):
    s=str(n)
    if len(s)==1:
        return len(fd[s])
    elif len(s)==2:
        if s[0]=='1':
            return len(teens[s])
        else:
            return len(td[s[0]]) + len(fd[s[1]])
    elif len(s)==3:
        if s[1:3]=='00':
            return len(fd[s[0]]) + len(hun['100'])
        elif s[1]=='1':
            return len(fd[s[0]]) + len(hun['100']) + len('and') + len(teens[s[1:3]])
        else:
            return len(fd[s[0]]) + len(hun['100']) + len('and') + len(td[s[1]]+fd[s[2]])
    elif s=='1000':
        return len('onethousand')

cnt = 0
for i in range(1,1001):
    cnt+=checkWords(i)
print cnt

이번 문제는 노가다성이 짙은 문제였다. 분명히 제대로 푼 것 같은데 정답이 아니라고 나와서 모든 숫자를 print해봤더니 100의 배수인 숫자들의 끝에 'and'가 붙어서 one hundred and, two hundred and 등으로 계산이 되고 있었다. 이것도 모르고 혹시 영어 알파벳이 틀렸나 하나하나 체크하고 있었으니... (사실 forty를 fourty로 잘못 알고 있긴 했다...)

풀고 보니 또 코드가 매우매우 지저분해 보인다. 각 숫자를 문자열로 변환하고, 길이를 계산하고, 각 자릿수의 인덱스를 사전에서 찾아오고... 그러고 보니 사전에다가 그냥 int 형을 넣으면 될 것을 전부 str 로 넣어놔서 코드가 더 지저분하다.

또 다른 사람들의 기가 막힌 코드들을 보며 반성해야지.


#Developed by hkapur97 on Project Euler
from math import log10

def problem17():

    d1 = {1:3, 2:3, 3:5, 4:4, 5:4, 6:3, 7:5, 8:5, 9:4, 1000:11}
    d2 = {11:6, 12:6, 13:8, 14:8, 15:7, 16:7, 17:9, 18:8, 19:8}
    d3 = {10:3, 20:6, 30:6, 40:5, 50:5, 60:5, 70:7, 80:6, 90:6}

    def l(n):
        return int(log10(n)//1 + 1)

    def f(n):

        if l(n) == 1 or l(n) == 4: return d1[n]
        if l(n) == 2 and 10 < n < 20: return d2[n]
        if l(n) == 2 and n % 10 == 0: return d3[n]
        if l(n) == 2: return d3[n/10 * 10] + d1[n % 10]
        if l(n) == 3 and n % 100 == 0: return d1[n/100] + 7
        if l(n) == 3 and 10 < n % 100 < 20: return d1[n/100] + d2[n % 100] + 10
        if l(n) == 3 and n % 100 < 10: return d1[n/100] + d1[n % 10] + 10
        if l(n) == 3 and n % 10 == 0: return d1[n/100] + d3[n % 100] + 10
        if l(n) == 3: return d1[n/100] + d3[(n % 100)/10*10] + d1[n % 10] + 10

    return sum([f(x) for x in xrange(1, 1001)])

[/python]

이 사람의 코드를 볼 때 마다 무릎을 친다. 인도가 수학과 프로그래밍에 뛰어나다더니... 몇 자리 수 인지 알아내기 위하여 로그를 이용하였고, 나머지 연산을 이용해서 100 이상의 숫자와 미만의 숫자를 구분하는 등 코드가 깔끔하다. 나는 왜 이런 생각도 못하고 정답 찾아내기에만 급급해서 막 코딩을 하였는가...

[python]

#Developed by johnnie on Project Euler
lens=[0,3,3,5,4,4,3,5,5,4,3,6,6,8,8,7,7,9,8,8,0,0,6,6,5,5,5,7,6,6,7,0]
t=11
for h in range(1,1000):
    d=h%100
    e=h//100
    f=d%10
    g=d//10
    if e>0:
        if d+f+g==0:
            t=t+lens[e]+lens[30]
        else:
            t=t+lens[e]+lens[30]+3
    if g>1:
        t=t+lens[g+20]+lens[f]
    else:
        t=t+lens[d]
print(t)

어느 미국인의 코드이다. 보통 사전을 이용해서 풀었는데 이 사람은 특이하게 리스트를 이용하여 문제를 풀었다.

내 코드는 각 숫자들을 직접 글자로 표현하고 코드 상으로 계산 과정을 보여줄 수 있다는 점에서는 다른 코드보다 나은 점이라고는 할 수 있지만 코드의 간결함과 창의적인 문제 해결 능력에서는 많이 뒤진 것 같다. 물론 위의 두 사람도 내가 짠 것 처럼 각 숫자들을 글로 정의하고나서 len()을 이용하여 풀 수도 있었겠지만 그 쪽으로는 크게 초점을 두지 않은 것 같다.

처음 문제를 봤을 떄, 그냥 노가다문제네 하고 별 생각 없이 풀었었는데 다른 사람들의 코드를 보니 또 한 수 배우게 된다.

  • partrita

    잘 배웠습니다:)