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

1676번 팩토리얼 0의 개수

문제

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

입력

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

출력

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

예제 입력 1 복사

10

예제 출력 1 복사

2

예제 입력 2 복사

3

예제 출력 2 복사

0

try1

//---- 세팅 ----//
const fs = require('fs');
const stdin = (
  process.platform === 'linux'
    ? fs.readFileSync('/dev/stdin').toString()
    : `\
3
`
).split('\n');

const input = (() => {
  let line = 0;
  return () => stdin[line++];
})();

//---- 풀이 -----//

const n = Number(input());

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

const factNumArr = String(factorial(n)).split('').map(Number);

let zeroCnt = 0;
for (let i = factNumArr.length - 1; i >= 0; i--) {
  if (factNumArr[i] !== 0) break;
  zeroCnt++;
}

console.log(zeroCnt);

로직은 간단하다.

팩토리얼을 계산해서 값을 구하고 값을 뒤에서 부터 하나씩 순회하며 0이 아닌 값이 나올 때 까지 카운트를 시작한다.

하지만 결과는 틀렸습니다이다.. 로직이나 코드에는 문제가 없어보이는데 어디서 왜 틀리는지 아직 모르겠다😂

검색을 해본 결과 팩토리얼을 사용하지 않고 푸는 문제인것 같다. 하지만 어떻게... 왜 틀렸다고 잡았는지는 아직도 모르겠다...

try2

//---- 세팅 ----//
const fs = require('fs');
const stdin = (
  process.platform === 'linux'
    ? fs.readFileSync('/dev/stdin').toString()
    : `\
3
`
).split('\n');

const input = (() => {
  let line = 0;
  return () => stdin[line++];
})();

//---- 풀이 -----//

const n = Number(input());

const solution = n => {
  let zeroCnt = 0;

  for (let i = 5; i <= n; i *= 5) {
    zeroCnt += Math.floor(n / i);
  }
  
  return zeroCnt;
};

console.log(solution(n));

팩토리얼 값의 뒤에 0이 나오려면 10이 곱해져야 한다.

10이 구해지려면 2나 5의 개수를 구해서 최소값을 구해야한다,

만약 2가 4개 5가 2개인 경우, 2와 5가 짝으로로 있어야 10이 되므로, 0의 갯수는 2개가 된다.

원래는 2와 5의 개수를 각각 구해, 적은 수를 출력해줘야한다. 하지만 2의 배수는 5의 배수보다 많기 때문에 5의 배수를 구하는게 최소값이 되므로 위에서는 5의 배수만을 구했다.

참고한 블로그 : https://leylaoriduck.tistory.com/512

이 블로그를 꼭 참고하자 설명을 잘 해 주셨다.