Leet Code - 172. Factorial Trailing Zeroes(C++)

포타토·2020년 2월 24일
1

알고리즘

목록 보기
56/76

예제: Factorial Trailing Zeroes

문제
Given an integer n, return the number of trailing zeroes in n!.

Example 1:

Input: 3
Output: 0
Explanation: 3! = 6, no trailing zero.

Example 2:

Input: 5
Output: 1
Explanation: 5! = 120, one trailing zero.

풀이

n!에서, 끝에 0이 붙는 개수를 return하는 문제이다.

당연히 n!을 반복문으로 풀어내면 0의 개수를 구하는것은 간단하다. 물론 그렇게하면 바로 time limit에 걸린다.

끝에 0이 나오려면 무조건 5가 곱해져야 하기 때문에, 팩토리얼을 몇 개 나누어 보니, 0의 개수는 sum(n을 인수분해 했을 때 나오는 5의 개수)(n : 1->n) 정도로 표현할 수 있게 되었다.

문제는 이를 어떻게 소스코드로 구현하느냐 인데.. 필자는 CASE1과 같이 구현하였다.
5씩 건너뛰며, 인수분해 했을 때 5의 개수를 계속 더해준 것이다.

통과는 했지만, 속도가 너무 느렸다.

다른 사람의 풀이를 보니, 충격의 CASE2번 풀이를 볼 수 있었다.
너무 간단한 코드기 때문에 딱 보아도 알 것이다. 규칙에도 정확히 들어맞는다. 참, 어떻게 저런 규칙을 찾았는지 신기하도다..

전체적인 소스코드는 아래와 같다.

소스 코드

/* CASE1 */
class Solution {
public:
	int trailingZeroes(int n) {
		int res = 0;

		for (long i = 5, j = 1; i <= n; i += 5, j++) {
			if (j == 5) {
				j = 0;  //초기화

				int num = i;
				while (num > 0 && num % 5 == 0) {
					res++;
					num /= 5;
				}
			}
			else {
				res++;
			}
		}

		return res;
	}
};

/* CASE2 */
class Solution {
public:
	int trailingZeroes(int n) {
		if (n == 0) return 0;

		return (n / 5) + trailingZeroes(n / 5);
	}
};

풀이 후기

이런 문제가 바로 필자에게 충격을 주는 문제이다. 왜 나는 저렇게 하지 못했는가! 하는 생각이 들곤 한다. 좀 더 생각을 유연하게 가지자

profile
개발자 성장일기

0개의 댓글