[Baekjoon] 1676 팩토리얼 0의 개수(파이썬/자바스크립트/NodeJs)

이번 문제는 아래 링크에서 풀어볼 수 있습니다.

1676번: 팩토리얼 0의 개수

---

문제

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

입력

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

출력

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

예제 입력 1

10

예제 출력 1

2

예제 입력 2

3

예제 출력 2

0

---

정답 코드

나의 답안(파이썬)

import sys

n = int(sys.stdin.readline().rstrip())


def mySolution(n):
    result = 1
    cnt = 0

    for i in range(1, n + 1):
        result *= i

    result = str(result)
    # length = len(result)
    # i = 0

    # while i < length:
    #     if result[length - 1] == "0":
    #         cnt += 1
    #     else:
    #         break

    #     length -= 1
    #     i += 1

    for i in reversed(result):
        if i == "0":
            cnt += 1
        else:
            break

    return cnt


print("mySolution", mySolution(n))

나의 답안(NodeJs/자바스크립트)

const fs = require('fs');
const filePath = process.platform === 'linux' ? '/dev/stdin' : './input.txt';
let input = fs.readFileSync(filePath).toString().trim();

input = parseInt(input);

const mySolution = (n) => {
    const factorial = (n) => {
        if (n === 0) return 1n;

        return BigInt(n) * factorial(n - 1);
    };

    let result = factorial(n);
    let cnt = 0;

    result = String(result);
    let length = result.length;
    let i = 0;

    while (i < length) {
        if (result[length - 1] === '0') cnt++;
        else break;

        length--;
        i++;
    }
    // for (let i = result.length - 1; i >= 0; i--) {
    //     if (result[i] === '0') cnt++;
    //     else break;
    // }

    return cnt;
};

console.log('mySolution', mySolution(input));

답안 1
파이썬 Ver.

import sys

n = int(sys.stdin.readline().rstrip())


def answer1(n):
    count = 0

    while n >= 5:
        count += n // 5
        n //= 5

    return count


print("answer1", answer1(n))

NodeJS/자바스크립트 Ver.

const fs = require('fs');
const filePath = process.platform === 'linux' ? '/dev/stdin' : './input.txt';
let input = fs.readFileSync(filePath).toString().trim();

input = parseInt(input);

const answer1 = (n) => {
    let count = 0;

    while (n >= 5) {
        count += Math.floor(n / 5);
        n = Math.floor(n / 5);
    }

    return count;
};

console.log('answer1', answer1(input));

 

답안 2
파이썬 Ver.

import sys

n = int(sys.stdin.readline().rstrip())


def answer2(n):
    return n // 5 + n // 25 + n // 125


print("answer2", answer2(n))

NodeJS/자바스크립트 Ver.

const fs = require('fs');
const filePath = process.platform === 'linux' ? '/dev/stdin' : './input.txt';
let input = fs.readFileSync(filePath).toString().trim();

input = parseInt(input);

const answer2 = (n) => {
    return Math.floor(n / 5) + Math.floor(n / 25) + Math.floor(n / 125);
};

console.log('answer2', answer2(input));

 

---

문제 풀이

 숫자 끝이 0이 되려면 5의 배수를 찾으면 된다. 즉 10!에서 5의 배수 개수는 10을 5로 나눈 몫(10//5)와 같다. 그런데 25, 125와 같이 5가 여러 번 반복되는 수가 있다. 이러한 수는 5로 나눈 몫에다 다시 한 번 더 5로 나눠주면 된다. 예를 들어 25의 경우 25를 5로 나눈 몫(25//5)인 5에서 다시 5로 나누면 추가로 등장한 횟수(5//5 = 1)를 구할 수 있다.

 나의 경우 이와 같은 수학적 원리를 이용하지 않았다. 일단 팩토리얼 결괏값을 구한 뒤 결괏값을 문자열로 바꾸어 끝에서부터 for 반복문을 돌린다. 탐색하는 문자가 0이라면 0의 등장 횟수 cnt를 1씩 증가시키고 0이 아닌 문자가 나온 시점에서 break를 걸어 반복문을 빠져나오는 식으로 코드를 짰다.

---

함께 보기

https://v3.leedo.me/devs/47

[알고리즘] 백준 1676번 팩토리얼 0의 개수 python

https://lucian-blog.tistory.com/84

[백준 1676번] (factorial)팩토리얼 0의 개수 in python