백준 1676번 - 팩토리얼 0의 개수(Node.js)

백준 1676번 - 팩토리얼 0의 개수(Node.js)

https://www.acmicpc.net/problem/1676

 

 

 

---

첫 번째 나의 풀이

	let fs = require('fs');
	let input = fs.readFileSync('/dev/stdin').toString().split(' ');
	inputs = Number(input)
	function Factorial(num){
	let answer = 1;
	let count = 0;
	for(let i = 1; i <= num; i++){
	answer *= i;
	}
	answer = String(answer).split("");
	for(let j = answer.length - 1; j >= 0; j--){
	if(answer[j] === "0"){
	count++;
	} else {
	break;
	}
	}
	return count;
	}
	console.log(Factorial(inputs))

view raw 백준1676번.js hosted with ❤ by GitHub

• 처음 내가 이 문제를 보고 생각한 것을 위의 코드를 보고 설명할 것이다.
• 9 ~ 11번째 줄은 입력된 N에 따라 N!을 계산하는 코드이다.
• 13번째 줄은 구한 N!의 값을 split() 메서드를 이용하여 하나씩 잘라주고 그 값을 answer에 넣어주었다.
  *split()메서드를 이용하기 위해서 문자열로 만드는 작업이 필요하기 때문에 String()을 사용하여 문자열로 만드는 작업을 해주었다.
• 15 ~ 21번째 줄은 위의 split() 메서드를 이용하여 자른 결과의 배열인 answer를 뒤에서부터 반복문을 사용하여 "0"이 나오면 count를 1씩 더해주고, "0"이 아닌 다른 문자가 나오면 break를 사용하여 반복문을 탈출하는 방법을 사용하였다.
• 23번째 줄은 count에 담긴 값을 return해준다.

 

• 나는 처음에 나의 로직에 아무 문제가 없다고 생각하고 계속 제출을 해봤지만, 계속해서 "틀렸습니다" 결과가 나왔다.
• 그래서, 입력을 잘못해주고 있나 생각하여 위의 1 ~ 3번째 줄만 주구장창 계속해서 바꿔주었지만, 결과는 어김없이 "틀렸습니다" ...

• 결국, 나는 30분넘게 나의 로직에 무엇이 잘못되었나 계속 생각하였고, RunJS 프로그램을 통해 입력값을 여러가지 입력값을 넣어보는 시도를 해보았다.
• 1부터 21까지 입력을 해보았고, 엥 ..? 입력값이 21을 넘는 순간 count값을 0을 반환하는 것을 알게되었다.

• 이 결과에 대한 이유에 대해서 나는 구글링을 해보았고, 찾아내었다.
• 그것은 바로 ..! JS는 -(2^53 -1) 와 2^53 -1 사이의 숫자값을 표현할 수 있기 때문에 이 범위의 값이 아니게 되면 Infinity로 표현이 된다.
• 따라서, 위의 Factorial(22)를 하게 되었을 경우 0이 반환되는 것이었다.

 

 

---

발견한 규칙

위의 사실을 알고 난 이후 나는 이 문제를 어떻게 접근할지 고민했고, 고민의 결과 어느 한가지 법칙을 알아내었다.

바로, 입력값이 5의 배수마다 맨 끝의 0의 개수가 한개씩 늘어나고,

5^n일 때 마다 맨 끝의 0의 개수가 n개 만큼 추가 된다.

따라서, 입력값이 1 ~ 4일 경우에는 0의 개수가 0개 / 5 ~ 9일 경우에는 0의 개수가 1개 / ... / 20 ~ 24일 경우에는 0의 개수가 4개 / 25 ~ 29일 경우에는 0의 개수가 6개 / ...

 

 

---

두 번째 나의 풀이

	let fs = require('fs');
	let input = fs.readFileSync('/dev/stdin').toString()
	inputs = Number(input)
	function Factorial(num){
	let answer = 0;
	while (num >= 5) {
	answer += parseInt(num / 5);
	num /= 5;
	}
	return answer;
	}
	console.log(Factorial(inputs));

view raw 백준1676번.js hosted with ❤ by GitHub

• 8 ~ 11번째 줄은 입력값이 1 ~ 4일 경우에는 당연히 실행되지 않고, answer의 초기값이 0이므로 0을 반환하고, 입력값이 5 이상일 경우에는 입력값을 5로 나누고 parseInt()를 사용하여 정수부분만 answer에 더해주고, 그 다음의 계산을 위해 입력값을 5로 나누어주는 작업을 하였다.
• 이렇게 하면 위의 법칙인 5의 배수마다 0의 개수가 하나씩 늘어나고, 5^n마다 0의 개수가 n개 만큼 추가 되는것을 해결할 수 있다.
• 예를들어, 입력값이 27일 경우,
  ① answer에는 parseInt(27/5)의 결과인 5가 더해진다.
  ② num에는 27/5에 해당하는 5.4가 담기게된다.
  ③ num이 5 이상이므로, 다시 while문을 실행하게 된다.
  ④ answer는 parseInt(5.4/5)의 결과인 1이 기존에 더해진 5에 더해지게 되어 6이된다.
  ⑤ num에는 5.4/5에 해당하는 1.08이 담기게된다.
  ⑥ num이 5 미만이므로, while문을 실행하지 않는다.
  ⑦ 따라서, 최종적으로 answer의 값인 6이 return 된다.

 

 

---

느낀점

ⓐ 처음에는 JS가 표현할 수 있는 숫자의 범위를 생각하지 않고, 무턱대고 풀어서 이런 결과가 나온 것 같다.

ⓑ 컴퓨터는 잘못하지 않는다 .. 내가 잘 못 생각할뿐 ..