[백준 1676번] 팩토리얼 0의 개수 - JavaScript

 

 

이 문제는 팩토리얼의 결과에서 0의 개수를 구하는 문제인데, 뒤에서부터 0의 개수이다.

 

문제를 보자마자 조금 의심되고 그냥 단순하게 푸는 건 아닐 거 같았기에, 조금 고민을 해보았지만 잘 생각나지 않아 일단 그냥 노가다로 풀어보았다.

 

 

노가다 코드

const input = require('fs')
	.readFileSync('/dev/stdin')
	.toString()
	.trim()
	.split('\n');

const value = +input;
const facVal = factorial(value);
const result = checkNumofZero(facVal);
console.log(result);

function factorial(n) {
	let result = 1;
	for (let i = 1; i <= n; i++) {
		result *= i;
	}
	return result;
}

function checkNumofZero(n) {
	let count = 0;
	let num = n.toString();

	for (let i = 0; i < num.length; i++) {
		if (num[num.length - 1 - i] === '0') {
			count++;
		} else if (num[num.length - 1 - i] !== '0') {
			break;
		}
	}
	return count;
}

 

 

결과는!!

 

 

ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ 그럼 그렇지.... 아무래도..........

 

그리고 고민을 좀 해보던 중 뒤에서부터 0의 개수면 10이 곱해진 개수이지 않나 ?? 라는 생각이 들었다.

 

그렇다면 10의 배수의 개수를 구하면 되겠구나!

 

 

근데 인터넷에 찾아본 결과 2의 개수는 많은 수에 포함되어 있기 때문에 5의 개수를 구하면 된단다!!

팩토리얼에서 5가 곱해진 개수를 구하려면 5의 거듭제곱을 팩토리얼할 수에 나눈 값들을 더하면 된다.

 

 

예를 들어, 100!을 예로 들면

• 100 / 5 = 20
• 100 / 25 = 3
• 100 / 125 = 0 (종료)

 

이러한 패턴이다.

팩토리얼을 수행할 수보다 5의 배수가 크면 몫이 0이 나오므로, 이때 종료하게 된다.

 

 

이제 코드를 보자.

 

소스 코드

const input = require('fs').readFileSync('/dev/stdin').toString().trim();

const n = +input;

function countTrailingZeros(n) {
	let count = 0;
	for (let i = 5; i <= n; i *= 5) {
		count += Math.floor(n / i);
	}
	return count;
}

console.log(countTrailingZeros(n));

 

코드가 훨씬 간단해졌다.

 

 

 

 

여담)

실제로 JavaScript에서 숫자 타입은 Number로 제한되어 있고, 15~16자리 이상의 큰 숫자를 정확히 표현하지 못한다고 한다.

따라서 큰 수의 경우 Factorial을 수행한 결과값이 이상할 수 있다는 것이다.