[LEETCODE] 172: Factorial Trailing Zeros(Python)

문제 설명

n이 주어질 때, n!에서 오른쪽에 위치하는 0의 개수를 구해보자.

나의 풀이

class Solution:
    def trailingZeroes(self, n: int) -> int:
        answer=0
        i=5
        while i<=n:
            answer+=n//i
            i*=5
        return answer

처음에는 선형 시간으로 풀리는 방법을 생각하다가, 어떤 지점에서 틀리는지 모르겠어서 답을 찾아보았다.

오른쪽에 0을 만들어내는 것은 10을 곱할 때이다. 10은 2*5로 이루어지며 즉 5의 배수가 등장하는 순간이 10이 곱해지는 순간이다.

하지만 5x5인 25의 경우, 5를 2번 곱하는 것이기 때문에 25의 배수도 고려해야 한다. 같은 논리로 5x5x5의 배수, 5x5x5x5의 배수… 를 고려해야 한다.

즉 5를 제곱해가며 n 이하인 배수의 갯수를 찾아내면 된다.

시간복잡도

i가 5배씩 변하기 때문에 시간복잡도는 O(log5(n))이다.