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.
[출처 - projecteuler.net/]
이번에는 조금 색다른 문제입니다. 기존에는 항상 숫자를 이용하여 무언가를 수행하는 문제였다면, 이번에는 숫자에 해당하는 알파벳을 가지고 그 길이는 도출하는 문제입니다. 뭔가 재미있어 보이지 않나요?? 그렇다면, 한번 고민해서 풀어보도록 하겠습니다.
해당 문제는 1 ~ 1000까지의 숫자를 표현하는 단어를 가지고 모두 나열하여 그 길이를 모두 더해서 그 결과를 제출하라는 문제입니다. 단 영국식 사용법을 적용하여 "and"를 백단위 표현과 십단위 표현 사이에 넣으라는 주의점도 잊으면 안됩니다.
우리가 생각해야 할 규칙성은 몇가지가 있습니다.
- 백단위 자리수를 생각하면, 1 ~ 99는 매번 반복이 됨
- 십단위 자리수를 생각하면, 1 ~ 9는 매번 반복이 됨
- 단, 십단위 자리수를 생각할때 11 ~ 19는 특유한 단어가 사용됨 (예외 조치가 필요함)
- 1,000에 대해서는 별도로 추가로 저장
정도가 되어 보입니다. 그렇다면 한번 코딩으로 구현해 볼까요?? 이 문제도 뭔가 최적화 없이 그냥 Basic으로 구현해 보겠습니다.
1. Basic
숫자를 알파벳으로 바꾸고 그 길이를 연산해야 하기 때문에... 아무래도 int형의 데이터를 string으로 변환할 필요가 있습니다. 따라서 그 매핑관계를 나타낼 table이 필요합니다. 저는 Python의 dictionary형을 사용하여 그 table을 만들어 보겠습니다.
num_dict = {0:'', 1:'one', 2:'two', 3:'three', 4:'four', 5:'five', 6:'six', 7:'seven', 8:'eight', 9:'nine'}은근 간단하죠?? 이와 동일하게, 규칙적이지 않은 기준에 대해서 또다른 dictionary가 필요합니다. 바로 10 / 20 / 30 .... 90에 해당하는 값들과 11~19까지의 불규칙적인 수에 대한 table입니다.
num_dict = {0:'', 1:'one', 2:'two', 3:'three', 4:'four', 5:'five', 6:'six', 7:'seven', 8:'eight', 9:'nine',
10: 'ten', 11: 'eleven', 12: 'twelve', 13: 'thirteen', 14: 'fourteen', 15: 'fifteen', 16: 'sixteen', 17: 'seventeen', 18: 'eighteen', 19: 'nineteen',
20: 'twenty', 30: 'thirty', 40: 'forty', 50: 'fifty', 60: 'sixty', 70: 'seventy', 80: 'eighty', 90: 'ninety'}몽땅 추가해 주었습니다.
그렇다면, 다음로직을 구현해 보겠습니다. 당장 여기서 생각해 볼 부분은... 백단위를 제외하고 0 ~ 99까지의 글자수 합 입니다. 왜냐하면, 한번 구해놓으면... 1xx에서도 2xx에서도 다 사용이 가능하기 때문입니다. 그리고 마지막에 1,000에 해당하는 알파벳 수만 더해주면 되겠죠??
우선 0 ~ 99에 대해서 출력하고 더하는 로직을 구현해 보겠습니다. 주의할 점은 아래와 같습니다.
- 우선 0 ~ 99에 대해서 loop를 수행하고, 각 값에 대해서 몫과 나머지... 그리고 추가적으로 set이라고 해서 입력값에서 나머지를 뺀 값을 구합니다. 그 이유는... thenty / thirty등과 같이 각 10자리의 알파벳을 구분하기 위함입니다.
- 몫이 0일 경우, 즉 10자리가 존재하지 않을경우는 나머지에 대한 알파벳만 출력
- 11~19 사이에 있거나, 10단위로 나누어 떨어질경우 그냥 입력 값에 대해서 바로 출력
- 그 외의 경우는, set에 대한 알파벳 및 나머지에 대한 알파벳을 출력
sum_0_99 = 0
for i in range(100):
mok = i // 10
remains = i % 10
set = i - remains
if mok == 0:
sum_0_99 += len(num_dict[remains])
print(num_dict[remains])
elif 11 <= i <= 19 or remains == 0:
sum_0_99 += len(num_dict[i])
print(num_dict[i])
else:
sum_0_99 += len(num_dict[set]) + len(num_dict[remains])
print(num_dict[set],num_dict[remains])
print(sum_0_99)이렇게 되면, 자연스럽게 0 ~ 99까지의 영어 알파벳이 출력되게 됩니다.
one
two
three
four
five
six
seven
eight
nine
ten
eleven
twelve
thirteen
fourteen
fifteen
sixteen
seventeen
eighteen
nineteen
twenty
twenty one
twenty two
twenty three
twenty four
twenty five
twenty six
twenty seven
twenty eight
twenty nine
thirty
thirty one
...
...
...
...
...이제 남은 부분은 100단위의 반복값을 구현하고, 예외만 처리해 주면 됩니다.
res = sum_0_99
for i in range(1, 10):
temp = num_dict[i] + 'hundredand'
print(temp)
# 100 처럼 찾는수가 100으로 나누어 떨어질 경우는 and가 붙지않기 때문에 3 빼줌
res += len(temp) * 100 + sum_0_99 - 3
print(res)여기서 주의할 점은, 해당 위치의 "num hundred and" 는 99번 붙고... 100으로 나누어 떨어지는 자리는 "and"를 빼주어야 합니다. 그래서 코드에서 "-3"이 들어가는 것 입니다.
onehundredand
twohundredand
threehundredand
fourhundredand
fivehundredand
sixhundredand
sevenhundredand
eighthundredand
ninehundredand뭐 로직은 잘 돌아가는 것 같습니다. 그럼 최종 코드 및 결과는 다음과 같습니다.
[소스코드]
import time
if __name__ == '__main__':
start = time.time()
num_dict = {0:'', 1:'one', 2:'two', 3:'three', 4:'four', 5:'five', 6:'six', 7:'seven', 8:'eight', 9:'nine',
10: 'ten', 11: 'eleven', 12: 'twelve', 13: 'thirteen', 14: 'fourteen', 15: 'fifteen', 16: 'sixteen', 17: 'seventeen', 18: 'eighteen', 19: 'nineteen',
20: 'twenty', 30: 'thirty', 40: 'forty', 50: 'fifty', 60: 'sixty', 70: 'seventy', 80: 'eighty', 90: 'ninety'}
sum_0_99 = 0
for i in range(100):
mok = i // 10
remains = i % 10
set = i - remains
if mok == 0:
sum_0_99 += len(num_dict[remains])
elif 11 <= i <= 19 or remains == 0:
sum_0_99 += len(num_dict[i])
else:
sum_0_99 += len(num_dict[set]) + len(num_dict[remains])
print(sum_0_99)
res = sum_0_99
for i in range(1, 10):
temp = num_dict[i] + 'hundredand'
print(temp)
# 100 처럼 찾는수가 100으로 나누어 떨어질 경우는 and가 붙지않기 때문에 3 빼줌
res += len(temp) * 100 + sum_0_99 - 3
res += len('onethousand')
print("결과 : ", res)
end = time.time()
print("소요시간 : ", end - start)
[결과]
결과 : 21124
소요시간 : 0.0다행히 무사 통과했습니다.
- Ayotera Lab -
댓글