이상하게 뭔가 쉽게 넘어가준 이번 문제...

1676: 팩토리얼 0의 개수

1. 내 풀이 1: 성공

import sys

num = int(sys.stdin.readline())

factorial = 1
for i in range(1, num+1):
    factorial = factorial * i

factorial = str(factorial)
result = 0
for i in range(len(factorial)-1, 0, -1):
    if factorial[i] == '0':
        result += 1
    else:
        break

print(result)

이 문제를 2번 풀었지만 팩토리얼을 계산하는데 차이가 있을 뿐, 실제 중요한 부분에 대한 로직은 전-혀 차이가 없다 ^^
팩토리얼이라 함은... 1부터 전부 곱한 것을 의미하므로 for문을 이용해 계산했다. 그리고 이를 문자열로 바꾼 후 뒤에서부터 0이 나올 때마다 result 변수에 더해준다.

간단...하다...

2. 내 풀이 2: 성공

from math import factorial
import sys

num = int(sys.stdin.readline())
fac = factorial(num)

fac = str(fac)
result = 0
for i in range(len(fac)-1, 0, -1):
    if fac[i] == '0':
        result += 1
    else:
        break

print(result)

이전에는 for문을 이용해 factorial을 계산했다면, 이번에는 math 모듈의 factorial을 이용해보았다. 메모리 측면이나 시간에서나 드라마틱한 변화는 없었다.

다른 블로그에서 봤는데 애초에 거꾸로 돌려주는 게 필요하다면,

for x in str(factorial(n))[::-1]:

를 사용하는 게 더 깔끔하게 표현되는 듯하다.

3. 다른 풀이

for문을 썼음에도! 내장함수를 썼음에도! 통과 시켜준 게 찜찜했기 때문에 다른 분들은 어떻게 풀었는지 한 번 찾아보았다.

아래의 블로그를 참고하였다.
https://mococoding.tistory.com/14

n = int(input())
def five_count(n):
    cnt = 0
    while n != 0:
        n //= 5
        cnt += n
    return cnt
    
print(five_count(n))

사실 처음엔 이거보고 하나도 이해가 안됐다 ㅋㅋㅋ while 문으로 계속해서 5로 나눠주는 이유가 약간 어렴풋이 이해됐다고 해야하나... 그래도 열심히 손으로 써보니 완벽 이해 완료.

핵심 아이디어는 5로 나눠지는 숫자들을 찾자! 이다.

5와 2만 있으면 짝수가 10, 즉 끝자리 0을 만들 수 있다. 더불어 1부터 어떤 수까지 차례대로 1씩 키우면 5의 개수보다 2의 개수가 많은 것은 자명하다. 그러므로 5의 개수만 세주면 되는 것이다.

그런데 문제는, 가끔 5를 2번 이상 품고 있는 친구들이라는 것이다. 가령, 25, 50, 75 등이 있다. 이런 숫자들은 count를 한 번씩 더 해줘야한다. 같은 맥락으로 125, 250 등은 2번씩 더 count를 해줘야한다.

그래서 while 문을 통해 계속해서 5를 나눠주게 되는 것이다. 여기까지는 나도 문제 없이 이해했다. 하지만 그래서 어떻게 25의 배수와 125의 배수를 찾겠다는 말인지 이해가 되지를 않았다. 답은 이렇다.

만일 100!의 끝자리 0을 찾아야 한다고 해보자. 그럼 100 이하의 숫자들 중 5로 나뉘어지는 숫자는,

5, 10, 15, 20, 25, 30, 35, 40, 45, 50,
55, 60, 65, 70, 75, 80, 85, 90, 95, 100

으로 총 20개가 있다. (100//5 = 20)

이 부분을 다르게 생각하면(모든 숫자를 5로 나뉘어보면),

1, 2, 3, 4, 5, 6, 7, 8, 9, 10,
11, 12, 13, 14, 15, 16, 17, 18, 19, 20

인 것이고, 여기서 5로 나뉘어지는 25, 50, 75, 100은 5, 10, 15, 20으로 나타나게 된다. 그래서 여기서 5를 한 번 더 나눠주면 또 5로 나뉘어지는 숫자를 찾을 수 있게 되는 것이다!

(여기까지 이해하는데 시간이 걸리다니 나란 인간 참...)

이 풀이를 돌려보니

훨씬까지는 아니더라도 조오큼..^^ 빨라졌다.

내가 이해가 안되는 부분을 자세하게 적다보니 길어졌군... 여튼 오늘도 신기한 알고리즘의 세계 끝!