[1676번] 팩토리얼 0의 개수

수학, 211116

문제

N!에서 뒤에서부터 처음 0이 아닌 숫자가 나올 때까지 0의 개수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N이 주어진다. (0 ≤ N ≤ 500)

출력

첫째 줄에 구한 0의 개수를 출력한다.

예제 입력 1

Plain Text
복사

예제 출력 1

Plain Text
복사

예제 입력 2

Plain Text
복사

예제 출력 2

Plain Text
복사

My solution

틀린 코드

정규표현식으로 0을 찾아낸다. 그리고 lastIndex로 그 위치를 잡는다. 문제는 100! 같은 큰 수는 lastIndex가 안 통한다. 그래서 틀렸다. 이게 안되는 게 이해가 안가서 찾아보았는데 BigInt로 변환하는 방식이 있었다. 정규표현식은 굳이 필요가 없었다. 배열화해서 for문으로 뒤에서부터 접근하면 된다. 최대한 for문을 사용하지 않으려다가 잘 안됐던 거 같다.

BigInt - JavaScript | MDN

는 원시 값이 안정적으로 나타낼 수 있는 최대치인 2^53 - 1보다 큰 정수를 표현할 수 있는 내장 객체입니다. BigInt는 정수 리터럴의 뒤에 n을 붙이거나( 10n) 함수 BigInt() 를 호출해 생성할 수 있습니다. BigInt와 는 어떤 면에서 비슷하지만 중요한 차이점이 있습니다. 예컨대 BigInt는 내장 객체의 메서드와 함께 사용할 수 없고, 연산에서 Number와 혼합해 사용할 수 없습니다.

https://developer.mozilla.org/ko/docs/Web/JavaScript/Reference/Global_Objects/BigInt

BigInt는 Number 원시 값이 안정적으로 나타낼 수 있는 최대치인 2^53 - 1보다 큰 정수를 표현할 수 있는 내장 객체입니다.

BigInt는 정수 리터럴의 뒤에 n을 붙이거나(10n) 함수 BigInt()를 호출해 생성할 수 있습니다.

function solution(i) {
    const input = i.toString().trim();

		const factorial = n => {
        if (n === 0) return 1n;
        return factorial(n - 1) * BigInt(n);
    };

    const res = factorial(+input)
        .toString()
        .split('');

    let flag = 0;
    for (let i = res.length - 1; i >= 0; i--) {
        if (+res[i]) break;
        flag++;
    }
		console.log(flag);
}
JavaScript
복사

2와 5가 몇개 나오는지 알아야 한다.

•

5의 개수가 항상 2의 개수보다 적기 때문에, 5의 개수만 세어주면 된다.

◦

5의 개수보다 많은 2가 있기 때문에 모든 5는 10처럼 0이 나오는 숫자가 된다. 그래서 5의 개수만큼 0이 나온다.

•

N!의 0의 개수 = [N/5] + [N/5의 제곱] + [N/5의 3제곱] + ...

소스코드

function solution(i) {
    const input = i.toString().trim();

    // # : 재귀
    // const factorial = n => {
    //     if (n === 0) return 1n;
    //     return factorial(n - 1) * BigInt(n);
    // };

    // const res = factorial(+input)
    //     .toString()
    //     .split('');

    // let flag = 0;
    // for (let i = res.length - 1; i >= 0; i--) {
    //     if (+res[i]) break;
    //     flag++;
    // }

    // # : 반복문, 5의 배수
    let flag = 0;
    let num = +input;

    while (num >= 5) {
        flag += Math.floor(num / 5);
        num /= 5;
    }

    console.log(flag);
		return flag.toString();
}

test('solution', () => {
    expect(solution(`10`)).toStrictEqual(`2`);
    expect(solution(`3`)).toStrictEqual(`0`);
    expect(solution(`0`)).toStrictEqual(`0`);
    expect(solution(`100`)).toStrictEqual(`24`);
});
JavaScript
복사