알고리즘 (6월 13일)

1. 문제 (코딩도장, 뒤쪽 0의 갯수 구하기)

https://codingdojang.com/scode/466?answer=28035#answer_28035 

코딩도장

---

2. 생각

이때 N!를 정수로 변환 해 뒤에서 부터 연속되는 0의 갯수를 구하세요.

 

1. 자연수 N 입력 받기
2. for문을 통해 factorial, N! 구하기
3. 나머지 연산자와 if문을 통해 일의자리가 0이면 countZero 값을 하나씩 더하고, 0이 아니면 while문에서 탈출한다.
4. 결과 출력

 

• 하지만, primitive data type만으로는 25! 의 숫자들을 모두 담을 수 없다는 문제점이 발생
• 이를 위해 무제한으로 정수 숫자들을 담을 수 있는 BigInteger 클래스를 이용
• BigInteger를 통해 long 타입의 범위 이상의 숫자들을 담을 수 있다.

 

---

3. 풀이 및 코드 분석

import java.util.Scanner;
import java.math.BigInteger;

public class countZero {
	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		
		// 입력 받기
		int N;
		while(true) {
			System.out.print("자연수 N을 입력하시오.:");
			N = scan.nextInt();
			
			if(N<1) {
				System.out.println("잘못입력하셨습니다.");
			}else {
				break;
			}
		}
		
		// bigInteger 클래스를 이용하여 factorial 계산
		BigInteger factorial = new BigInteger("1");
		
		for(int i=2; i<=N; i++) {
			factorial = factorial.multiply(BigInteger.valueOf(i));
		}
		
		// 뒷자리 0의 갯수 계산
		int countZero = 0;
		BigInteger ten = new BigInteger("10");
		BigInteger units;
		
		while(true) {
			units = factorial.remainder(ten);
			if(units.intValue()==0) {
				countZero++;
				factorial = factorial.divide(ten);
			}else {
				break;
			}		
		}
		
		// 결과 출력
		System.out.printf("뒤쪽 0의 갯수: %d", countZero);
	}
}

---

4. 메모

• BigInteger 클래스는 primitive data type과 다르게 무한히 많은 숫자들을 담을 수 있다.
• BigInteger 가 무한히 많은 숫자들을 담을 수 있는 이유는 문자열(String) 형태로 숫자를 받고 저장하기 때문이다.
• 따라서 BigInteger를 가지고 사칙연산하기 위해서는 BigInteger 클래스에서 제공하는 메소드를 이용해야한다.
• https://jbhdeve.tistory.com/69?category=1027193