172. Factorial Trailing Zeroes

172. Factorial Trailing Zeroes

 

class Solution:
    def trailingZeroes(self, n: int) -> int:
        # 펙토리알 구하는게 아니라.
        # 펙토리알 구해서 끝부분의 0의 개수 구하는..
        if not n:
            return 0

        def factorial(n):
            if n ==1:
                return 1
            return n * factorial(n-1)

        fac = factorial(n) 

        zero_cnt = 0
        while (fac % 10 == 0):
            zero_cnt += 1
            fac //= 10
        
        return zero_cnt

 

통과는 하는데, 시간 오래 걸림

 

네, 맞습니다. 제공된 코드의 문제는 팩토리얼 값을 직접 계산하고 나서 끝부분의 0의 개수를 계산하기 때문에 매우 비효율적입니다. 특히, n이 커질수록 팩토리얼 값 자체가 어마어마하게 커지기 때문에 메모리와 시간이 과도하게 소요됩니다.

---

문제점

1. 팩토리얼 계산의 비효율성:
   • 팩토리얼은 n!로 표현되며, n이 커질수록 값이 기하급수적으로 커집니다.
   • 예를 들어, 100!은 158자리 숫자가 됩니다. 이를 계산하고 끝부분의 0을 세는 것은 비효율적입니다.
2. 문제 해결의 초점:
   • 팩토리얼 값 자체를 계산할 필요가 없습니다.
   • 팩토리얼에서 끝부분의 0의 개수는 10의 배수(즉, 2와 5의 곱)의 개수로 결정됩니다.
   • 팩토리얼에는 항상 2의 배수가 5의 배수보다 많으므로, 5의 배수 개수만 세면 됩니다.

---

효율적인 해결 방법

5의 배수를 세는 방식으로 끝부분의 0의 개수를 구합니다.

이 방법은 매우 빠르고 효율적이며, O(n)의 시간 복잡도를 O(log₅n)으로 줄입니다.

 

class Solution:
    def trailingZeroes(self, n: int) -> int:
        # 펙토리알 구하는게 아니라.
        # 펙토리알 구해서 끝부분의 0의 개수 구하는..
        # 그런데, 펙토리알 모두 구해서 0 개수 구하면 너무 비효율적
        # 그래서 10의 개수를 세면되는데, 
        # 2의 개수는 5의 개수보다 많으니,
        # 결국 10의 개수를 구하는 것은 5로 몇번 나누어 지느냐? 의 개수 임

        if not n:
            return 0

        zero_cnt = 0
        for i in range(1, n+1):
            num = i
            while num % 5 == 0: # 나누어 떨어지면
                num //= 5
                zero_cnt += 1
        
        return zero_cnt

 

최적화 된 코드 

 

class Solution:
    def trailingZeroes(self, n: int) -> int:
        count = 0
        # 5의 배수 개수를 누적
        while n > 0:
            n //= 5  # n을 5로 나눠서 몫을 구함
            count += n
        return count