172번 Factorial Trailing Zeroes 풀이(c++)

풀이 해설을 요청하신 분이 있어서..

이 문제는 'trailing zero'을 구하는 문제이다.

숫자의 가장 뒤에 연속해서 붙어오는 0의 갯수를 세는 문제라고 말해도 될것같다.

(단 0인경우에는 숫자를 세지 않는다)

 

처음에는 주어진 숫자를 문자열로 바꿔서 맨 뒤에 있는 0의 갯수를 세는걸로 생각했지만,

더 효율적인 방법이 있을거라 판단하고 생각하다보니 한 가지 규칙을 발견하게 되었다.

 

n! = x * 10^r

 맨 뒤에 연속해서 오는 숫자가 r이라고 할 때, 위와 같은 수식으로 문제를 바꿔서 표현할 수 있다. 오히려 '맨 뒤에 있는 0의 갯수'보다 위 식이 훨씬 간결하고 정확하게 문제를 정의하고 있다. 즉, n!을 소인수분해하여 나오는 10의 갯수가 이 문제의 정답이 된다.

 

 10을 소인수분해하면 '2*5'임을 알 수 있는데, 2를 인수로 갖는 숫자는 짝수이고, 5를 인수로 갖는 숫자는 5의 배수임을 알 수 있다. 즉, 인수 2의 갯수가 5의 갯수보다 항상 많기 때문에 5의 갯수만 생각하면 그것이 10의 갯수랑 동일하다.

 

 이때 n=>n! 이므로, n을 5로 나누었을 때의 몫이 1부터 n까지의 수 중에서 '1개 이상의 5를 인수로 갖는 수'임을 알 수 있다. 예를 들어 n이 첫번째 5의 배수인 5보다 작은 경우, n을 5로 나누었을때의 몫은 0이다. 첫번째 5를 갖는 5부터 n/5의 몫은 1이 되고, 10이 되는 순간 n/2의 몫은 2가 된다. 여기서 '1개 이상의 5'라는 단어를 사용하였는데, 한가지 수에 2개 이상의 5를 가지는 경우도 생길 수 있다. 5의 제곱의 경우 한 숫자에 2개의 5를 인수로 가지게 된다.

 

 1~n범위에 n의 제곱수중 지수가 가장큰 수까지 처리하기 위해 재귀함수를 이용해 문제를 해결하였다. n을 5로 나누면 '1개 이상의 5를 인수로 갖는 수'를 알 수 있고, n을 5의 제곱으로 나누면 '2개 이상의 5를 인수로 갖는 수'를 알 수 있다. 이렇게 나누는 5를 계속 제곱시켜 몫이 0이 나올때까지 함수를 반복하고, 함수의 반환값이 0이 나오는 순간 지금까지의 모든 연산을 더해 결과를 제출하였다.

 

 

코드

    int devideFive(int n){
        if(n<=0) return 0;
        return devideFive((int)n/5) + (int)n/5;
    }
    int trailingZeroes(int n) {
        return devideFive(n);
    }

 

 

 

Factorial Trailing Zeroes - LeetCode