[Leetcode] Factorial Trailing Zeroes

거의 2년만에 해보는 PS 포스팅...

 

문제

난이도: medium

문제 링크: https://leetcode.com/problems/factorial-trailing-zeroes/description/

Given an integer n, return the number of trailing zeroes in n!.
Note that n! = n * (n - 1) * (n - 2) * ... * 3 * 2 * 1.

0과 10000사이의 수 n이 주어졌을 때 n의 팩토리얼인 n!에서 0이 몇개 들어가 있는지 그 갯수를 구하는 간단한 문제 입니다. (단 n = 0일대 0의 갯수는 0입니다)

 

 

Solution 1

0의 갯수를 새는 방법은 간단합니다. n! = a * 10^b 라면 0의 갯수는 10의 제곱수인 b가 됩니다.

그렇기 때문에 n!이 더이상 10으로 나누어 떨어질 때 까지 10을 계속 나누면서 카운팅을 해주면 됩니다.

int solution(int n)
{
    int ans = 0;
    int x = 1;
    for(int i = 1; i <= n; i++)
        x *= i;
    while(x%10 == 0) {
        ans++;
        x /= 10;
    }
    return ans;
}

 

하지만 n=10000일 때의 n!값은 int는 커녕 long long을 아득히 넘는 숫자이기 때문에 이런식으로 문제를 푸는 것을 사실상 불가능 합니다. 그렇기 때문에 n!값을 계산하기 보다는 1부터 n까지 순회하면서 각 숫자가 2를 곱한 갯수와 5를 곱한 갯수를 구해 모두 취합 한 다음, 2를 곱한 갯수와 5를 곱한 갯수 중 작은 갯수를 정답으로 출력하면 됩니다.

 

예를 들어 4!이 있다고 한다면 1 * 2 * 3 * 4 * 5가 됩니다. 여기서 1은 아무것도 없고, 2는 2가 1개, 3도 아무것도 없고, 4는 2가 2개 있습니다(2^2=4) 그리고 마지막으로 5는 5가 하나 있습니다.

여기서 2의 갯수와 5의 갯수를 모두 취합하면, 2는 3개(2, 2^2), 5는 1개가 됩니다.

2는 3개나 있지만 5는 1개밖에 없으므로 여기서 10의 1제곱까지만 구할 수 있고, 제곱수는 곧 정답을 의미하므로 n=5일 때 정답은 1이 됩니다. 실제로 5!은 120으로 0이 하나 있습니다.

int solution(int n) {
    int cnt_2 = 0, cnt_5 = 0;

    for(int _k = 1; _k <= n; _k++) {
        int k = _k;
        
        while(k%2 == 0) {
            cnt_2++;
            k /= 2;
        }

        while(k%5 == 0) {
            cnt_5++;
            k /= 5;
        }
    }
    return min(cnt_2, cnt_5);
}

 

n이라는 숫자가 있을 때 a라는 인자를 가지고 있는지 그리고 몇제곱 까지 있는지 구하는 방법은 간단합니다. 그냥 n이 a으로 나누어 떨어지지 않을 때 까지 계속 a로 나누면서 동시에 갯수를 카운팅 하면 됩니다.

 

 

Solution 2 (최적화)

Solution 1의 방식은 어떻게 보면 가장 무식하지만 n의 범위가 작기 때문에 충분히 통과되는 코드 입니다.

하지만 뭔가 찝찝합니다. 2중 반복문이 들어가 있으니까요.

n이 10000이니까 속도가 빨라 보일 뿐이지 n의 범위를 좀만 늘려도 시간이 오래 걸릴 께 눈에 선합니다.

하지만 이 이중 반복문을 사용하지 않고도 풀수 있는 방법이 또 존재합니다.

 

아까 서술했다시피 n!에서의 0의 갯수는 10의 제곱수와 같다고 했습니다. 또한 10 = 2 * 5가 되구요

근데 생각을 좀만 해보면 2는 n이 짝수가 될 때마다, 즉 2의 배수가 될 때마다 추가가 되지만, 5의 경우 5의 배수가 될 때마다 추가가 됩니다. x제곱으로 인해 5의 갯수가 x개로 갑자기 훅! 들어온다 치더라도 이미 이전에 2도 마찬가지로 x개가 훅! 들어왔을 것입니다. 즉, n!에서 2의 갯수는 5의 갯수보다 항상 더 많이 있습니다.

int solution(int n) {
    int cnt_5 = 0;
    for(int _k = 1; _k <= n; _k++) {
        int k = _k;
        while(k%5 == 0) {
            cnt_5++;
            k /= 5;
        }
    }
    return cnt_5;
}

 

그렇기 때문에 위와 같이 2의 갯수를 세재 않고 5의 갯수만 세는 코드가 실제로 통과가 되기도 합니다. 더이상 2에 대해 따로 계산을 하지 않기 때문에 어느정도 최적화가 되어 있다고는 하지만 2중 반복문인 것은 여전합니다.

 

다시 생각해 봅니다

아까 서술했다시피 n!에서의 2의 갯수는 더이상 의미가 없습니다. 5의 갯수만 생각하면 됩니다.

그리고 이 n은 5의 배수가 될 때마다 n!에서 5가 추가로 생겨납니다.

n의 범위	n!에서의 5의 제곱 갯수	n!에서의 0의 갯수
1 <= n <= 4	0	0
5 <= n <= 9	1 (0+1)	1
10 <= n <= 14	2 (1+1)	2
15 <= n <= 19	3 (2+1)	3
20 <= n <= 24	4 (3+1)	4
25 <= n <= 30	6 (4+2)	6

n = 1, 5, 10, 15, 20 까지 차례대로 1씩 카운팅 되어있습니다. 마찬가지로 0의 갯수도 1씩 카운팅 되어있겠죠

하지만 n=25일 때는 1이 아니라 2가 카운팅 되어있는데 그 이유는 25는 5의 제곱이기 때문에 5가 2개가 추가로 들어갔기 때문입니다. 즉, n이 5의 배수가 될 때 단순히 1씩 카운팅 하는 것이 아니라 5의 제곱 갯수대로 카운팅을 하는 것입니다.

추가로 예를 들어 n=50이 되면 50=2*(5^2)이므로 2개가 추가가 되고, n=125면 125=5^3이므로 3개가 추가가 될 것입니다.

 

int solution(int n) {
    int count = 0;
    int num = 5;
    while(n / num) {
        count += n/num;
        num *= 5;
    }
    return count;
}

 

결국 n!에서 5의 제곱 갯수는 n보다 작으면서 5의 제곱 수들을 차례대로 나눈 값의 합이 됩니다.

예를 들어 n = 25의 경우 n을 5로 나누면 5가 되고 또한 n를 25로 나누면 1이 되므로 0의 갯수는 5+1=6이 됩니다.

이렇게 해서 이중 반복문을 사용하지 않고도 최적화를 할 수 있게 되었습니다.

 

끗

이번 문제는 어떠한 알고리즘 지식을 요구하지 않는 상당히 쉬운 문제였지만, 최적화를 시도한다면 나름 문제해결력을 요구하는 문제이기도 했습니다. 알고리즘을 활용하여 푸는 문제도 좋긴 하지만, 이렇게 순수 문제해결력을 요구하는 문제를 푸는 것도 PS공부에 도움이 될 것같다는 생각이 드네요.