172. Factorial Trailing Zeroes

Factorial Trailing Zeroes - LeetCode

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이 존재하게 된다.

 

첫 번째 조건까진 빠르게 생각했지만 두 번째 조건은 생각하지 못했다...