[Node.js] 구름 level 2_어려운 문제

문제

https://level.goorm.io/exam/49054/%EC%96%B4%EB%A0%A4%EC%9A%B4-%EB%AC%B8%EC%A0%9C/quiz/1

구름LEVEL

 

 

풀이

이 문제는 팩토리얼 처리를 BigInt를 사용해 할 수 있는지와 팩토리얼을 구할때 최적화를 할 수 있는지 테스트하는 문제이다.

 

우선 BigInt의 경우는 팩토리얼된 값의 수 각각을 더해줘야 하기에 모든 수가 필요하다. 이렇게 되면 팩도리얼 계산 특징상 수의 크기는 기하급수적으로 커지게된다. 기존 Number 타입으로 표현할 수 있는 크기를 넘게된다. 그렇기에 BigInt를 이용해 계산해준다.

 

팩토리얼 계산도 주의해야 한다. 처음에는 재귀 함수를 이용해 팩토리얼을 구했지만, 한개의 케이스에서 런타임 에러가 발생했다. 아마 입력되는 값의 크기가 큰 케이스라 예상된다. 이 케이스에서 재귀 함수를 이용하면 시간복잡도가...... 

그래서 for문을 이용해 O(N) 시간복잡도를 갖는 팩토리얼 계산 식을 구현했다.

let factNum = BigInt(1);

for(let i = 2; i <= num; i++){
  factNum *= BigInt(i);
}

 

구해진 팩토리얼 BigInt값의 각 자리수를 더해야 하는 로직은 %(나머지 연산자)를 이용했다. BigInt값 % 10n을 한다면 1의 자리수만 구해진다. 그 다음 BigInt값 / 10n을 하면 소수점을 버리는 BigInt 특성을 이용해 한 자릿수씩 제거할 수 있다.

 

실패한 코드

// Run by Node.js
const readline = require('readline');

const fact = (n) => {
	return (n != 1n) ? n * fact(n - 1n) : 1n;
};

(async () => {
	let rl = readline.createInterface({ input: process.stdin });
	
	for await (const line of rl) {
		let num = BigInt(+line);
		let factNum = fact(num);
		
		while(factNum >= 10n){
			let sum = BigInt(0);
			let temp = factNum;
			while(temp > 0n){
				sum += temp % 10n;
				temp = temp / 10n;
			}
			factNum = sum;
		}
		console.log(factNum.toString())
		rl.close();
	}
	
	process.exit();
})();

 

성공한 코드

// Run by Node.js
const readline = require('readline');

(async () => {
	let rl = readline.createInterface({ input: process.stdin });
	
	for await (const line of rl) {
		const num = +line;
		let factNum = BigInt(1);
		for(let i = 2; i <= num; i++){
			factNum *= BigInt(i);
		}
		
		while(factNum >= 10n){
			let sum = BigInt(0);
			let temp = factNum;
			while(temp > 0n){
				sum += temp % 10n;
				temp = temp / 10n;
			}
			factNum = sum;
		}
		console.log(factNum.toString())
		rl.close();
	}
	
	process.exit();
})();