172. Factorial Trailing Zeroes

문제설명

• 특정 숫자 n이 주어졌을 때, n!의 값에서 0의 개수를 구하는 문제이다.

나의 접근

0의 개수: 소인수 2,5의 개수의 영향을 받음!
그중 5의 개수만 새어도 상관이 없다!

n이라는 정수가 주어졌을때, 1~n까지의 범위에서 항상 2의 배수가 5의 배수보다 많거나 같기 때문이다. 2와 5가 각각 한세트씩 있어야 '0'이 생기기에 5의 역할이 중요한 것이다.

soltion 1

1부터 n까지 반복문으로 5의 배수 찾기

---

class Solution {
public:
    int trailingZeroes(int n) {
        int total = 0;
        for(int i = n ; i >= 0 ; i--){
            int temp = i;
            while(temp / 5 > 0 && temp % 5 == 0){
                total++;
                temp /= 5;
            }
        }
        return total;
    }
};

---

가장 중요한 포인트는 while문 안에 있는 조건인데, "temp / 5 > 0 && temp % 5 == 0"
의 의미 자체는 1~n사이의 수 i가 5의 배수인가를 판별하는 과정이다. 특히 25와 125 등과 같은 5의 거듭제곱인 경우에 5를 소인수로 한개 이상 가지고 있는 경우에는 위와 같은 조건으로 사용해야한다.

더 좋은 방법

---

int trailingZeroes(int n){
    int count=0;
    
    for(int i = 5; i <= n ; i *=5){
        count += n/i;
    }
    return count;
}

---

해당 코드는 1~n을 모두 접근하는 것이 아닌, 특정 n에서 5, 25 등의 5의 거듭제곱을 나누는 과정이다.
이로서 1~n까지의 5의 배수의 개수, 25의 배수의 개수를 더 효율적인 방법으로 구할 수 있게된다.