사실 살면서 이런걸 궁금해 할 이유가 있을까 싶긴 하지만, 그래도 정말 뇌를 깨워주는 문제 같아서 소개하려고 합니다. 은 몇 개의 연속된 꼬리 0을 가지고 있을까요? 연속된 꼬리 0이라는 정의는, 만약 130500이면 연속된 꼬리 0은 2개이고, 10000은 4개의 연속된 꼬리 0을 가지는 것입니다. 즉, 주어진 이 10의 몇승으로 나눠 떨어지는가의 문제입니다.
가장 간단하게 생각할 수 있는 방법은 실제 factorial을 구해서 나누어 떨어지지 않을때까지 10으로 나눠보는 방법입니다.
def factorial(n):
if n == 1 or n == 2:
return n
else:
result = 1
while n > 1:
result *= n
n -= 1
return result
def numTrailingZeros(n):
num = factorial(n)
count = 0
while num % 10 == 0:
count += 1
num /= 10
return count
>>> from time import time
>>> t0 = time()
>>> print numTrailingZeros(10000)
2499
>>> print "걸린시간 : %.2e" % (time()-t0)
걸린시간 : 2.82e-01이 방법은 n이 커질수록 감당이 안될정도로 느려지게 됩니다. 어떻게 하면 스마트하게 계산해 낼 수가 있을까요? 아마 똑똑하신 분들은 짐작하시겠지만, 10은 2와 5의 곱으로 이루어진다는 점을 생각하는 것입니다. 그리고 조금 더 생각해보면 2가 곱해진 수가 당연히 5가 곱해진 수보다 많을 것입니다. (극단적으로 2의 배수가 5의 배수보다 많잖아요? ^^) 그럼 결국 5가 몇번 곱해졌느냐가 꼬리 0의 개수라는 의미겠죠?
1부터 n까지 중에 5의 배수는 몇개가 있을까요? 답은 간단합니다. 개가 존재합니다. 그럼 5를 다 찾은 걸까요? 아니요~ 25의 배수는 5가 기본적으로 2번씩 곱해진 수겠지요? 그럼 다음 5들은 개가 존재할 것입니다. 이런식으로 쭈욱 가면 결국 몫이 0이 될 때까지 나오는 몫들을 모두 더해주면 꼬리 0의 개수를 쉽게 구할 수 있겠지요? 충격적인 결과는 곧 확인하실 수 있습니다…
def smart_numTrailingZeros(n):
count = 0
while n > 0:
n /= 5
count += n
return count
>>> from time import time
>>> t0 = time()
>>> print numTrailingZeros(10000)
2499
>>> print "걸린시간 : %.2e" % (time()-t0)
걸린시간 : 2.10e-04우와…. 거의 1000배 가까이 빠르죠..? n이 더 커질수록 그 효율성은 훨씬 더 대단해질 것입니다. 정말 이 문제를 보고 똑똑해져야겠다는 생각을 많이 했습니다…