[leetcode] 172. Factorial Trailing Zeroes - C

문제

Factorial Trailing Zeroes - LeetCode

• 분류 - 브루트포스, ?
• 난이도 - Medium

---

문제 설명

n이 주어졌을 때, n! 값의 끝에 연속된 0이 몇 개 오는지 구하는 문제

즉, n! 값이 10으로 몇 번 나누어 떨어지는지 구하면 된다.

---

접근 방법

n!의 인수 중 10을 만드는 인수인 2와 5가 몇 번 등장하는지 구하고, 2의 개수와 5의 개수와 중 더 적은 개수가 답이 된다.

이때, 2는 모든 짝수의 인수이므로 반드시 2가 5보다 많다. 따라서 5의 개수만 구하면 된다.

 

관련 개념

Trailing Zero

Trailing zero - Wikipedia

이해는 안 되지만.. 혹시 나중에 다시 보면 이해 될지도 모르니 첨부

---

답안 코드 1 - 브루트포스

가장 기초적인 접근 방법으로, 2와 5의 등장횟수를 모두 세고, 더 적은 등장횟수를 반환하는 과정을 전부 나타낸 코드

메모리: 5.4 MB , 시간: 11 ms

int trailingZeroes(int n){
    int cnt2=0, cnt5=0;
    
    for(int i=n; i>=1; i--){
        int j=i;
        while(j%2 == 0){
            j = j/2;
            cnt2++;
        }
        while(j%5 == 0){
            j = j/5;
            cnt5++;
        }
        
    }
    
    if(cnt2 == 0 || cnt5 == 0) return 0;
    else if(cnt2 > cnt5) return cnt5;
    else return cnt2;
}

 

답안 코드 2

5의 등장횟수만 구한 코드

Runtime: 2 ms (64.81%), Memory Usage: 5.6 MB

int trailingZeroes(int n){
    int cnt=0;
    while(n>0){
        cnt += n/5;
        n = n/5;
    }
    return cnt;
}

 

답안 코드 3

답안코드2와 같은 원리지만, 연산횟수를 줄여 최적화한 코드

Runtime: 0 ms (100%), Memory Usage: 5.6 MB (46.30%)

int trailingZeroes(int n){
    int cnt=0;
    while(n>0){
        cnt += n/5;
        n = n/5;
    }
    return cnt;
}