[백준] 1676번 팩토리얼 0의 개수 (실버5)

 

팩토리얼 값에서 0의 개수 구하기

---

주어진 숫자 n에 대한 팩토리얼 값에서 처음 0이 아닌 숫자가 나왔을 때 그전까지의 0의 개수를 구하는 문제입니다.

 

 

 

 

내가 생각한 방법

---

n에 대한 팩토리얼 값을 계산한 뒤, 이를 문자열로 변환하여 맨 뒤에서부터 0이 아닌 숫자가 처음 나오는 인덱스를 찾고, 이를 전체 문자열 길이에서 빼주면 0의 개수를 구할 수 있을 것이라 생각했습니다.

따라서 다음과 같이 코드를 작성해 보았습니다.

static int getFactorialNum(int num) {
    int result = 1;
    for(int i=2; i<= num; i++) {
        result *= i;
    }
    return result;
}

static int getZeroCount(int num) {
    Integer factNum = getFactorialNum(num);
    String strFactNum= factNum.toString();
    int n1 = 0;
    int result = 0;
    for(int i = strFactNum.length() - 1; i >= 0; i--) {
        if(strFactNum.charAt(i) != '0') {
            n1 = i;
            break;
        }
    }
    result = (strFactNum.length() - 1) - n1;
    if(n1 == 0) {
        result = 0;
    }
    return result;
}

 

 

문제점

---

위 코드로는 작은 숫자에 대해서는 정확한 결과를 도출할 수 있지만, 팩토리얼 값이 매우 커지는 경우에는 정확한 결과를 도출하지 못하는 경우가 있습니다. 예를 들어, 20! 의 경우 팩토리얼 값이 매우 커져서 int 타입으로 표현이 불가능해지며, 이를 문자열로 변환하여 저장하더라도 음수 값이 저장됩니다.

 

 

 

개선 방법

---

위 코드의 문제점을 개선하기 위해서는 팩토리얼 값을 계산할 때, 이를 저장하는 자료형을 BigInteger로 변경하여야 합니다. BigInteger는 매우 큰 정수 값을 다루는 데 사용되며, 이를 이용하면 매우 큰 수에 대한 팩토리얼 값을 정확하게 계산할 수 있습니다.

따라서 다음과 같이 코드를 수정할 수 있습니다.

 

 

import java.math.BigInteger;

   static BigInteger getFactorialNum(int num){

        BigInteger result = BigInteger.ONE;
        for(int i=2; i<= num; i++){
            result = result.multiply(BigInteger.valueOf(i));
        }
        return result;
    }


static int getZeroCount(int num) {

        String strFactNum= String.valueOf(getFactorialNum(num));
        int n1=0;
        int result=0;



        for(int i=strFactNum.length()-1; i>=0; i--){
            if(strFactNum.charAt(i)!='0') {
                n1=i;
                break;
            }
        }

        result = (strFactNum.length()-1)-n1;

        if(n1==0) result=0;

        return result;
    }