172. Factorial Trailing Zeroes
[Factorial Trailing Zeroes - LeetCode
Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview.
leetcode.com](https://leetcode.com/problems/factorial-trailing-zeroes/)
1. 틀린 풀이
class Solution:
def trailingZeroes(self, n: int) -> int:
return n // 5
N이 주어지고 N! 의 0의 개수를 반환하는 문제다.
처음에는 DP 인가라고 생각을 했다가 좀 더 쉽게 생각할 수 있는 문제인 것 같았다.
0이 만들어지려면 10이 곱해져야 한다. 그리고 10은 2와 5의 곱이다. 즉 2와 5의 곱의 쌍이 몇 개인지를 구하면 된다고 생각했다.
또 2는 5가 곱해지기 전에는 충분히 많이 곱해지기 때문에 결국 5의 개수만 세면 되지 않을까라는 생각을 했다.
하지만 예외를 고려하지 못했다.
2. 답
class Solution:
def trailingZeroes(self, n: int) -> int:
answer = 0
cur = 5
while cur <= n:
answer += n // cur
cur *= 5
return answer
아래와 같은 경우를 추가적으로 고려해야 한다.
25! 의 경우를 생각해보자.
25를 곱하기 때문에 5를 2번 곱해준다. 그래서 0이 2개 늘어난다.
위와 같은 경우가 있기 때문에 5의 제곱수에 대해서도 0이 1개 늘어날 수 있다.
30! 을 예로 들면 다음과 같다.
30! 이 될 때까지 5는 30 / 5 = 6번만큼 곱해진다
또 30 / 5*5 = 1 만큼 5의 제곱수인 25가 곱해진다.
그래서 6 + 1 = 7개의 0이 존재하게 된다.
첫 번째 조건까진 빠르게 생각했지만 두 번째 조건은 생각하지 못했다...