[Java] baekjoon_1676 : 팩토리얼 0의 개수

수학

팩토리얼 0의 개수 : Silver5

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

1676번: 팩토리얼 0의 개수

 

 

 

첫 번째 작성 코드

import java.io.*;
import java.util.*;

public class Main {
  public static void main(String[] args) throws Exception {
    
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

    int n = Integer.parseInt(br.readLine());

    int num = 1;
    int cnt = 0;

    for (int i = 1; i <= n; i++) {
      num *= i;
    }

    String numStr = String.valueOf(num);

    for (int i = 0; i < numStr.length(); i++) {
      if (numStr.charAt(i) == '0') {
        cnt++;
      }
    }

    bw.write(String.valueOf(cnt));
    bw.newLine();
    bw.flush();
    bw.close();
  }
}

 

ㄴ 주어지는 N이 500까지의 범위의 수 이므로 팩토리얼 수가 매우 커져 int 범위를 넘어갈 수 있음을 확인

 

 

두 번째 작성한 코드

import java.io.*;
import java.util.*;

public class Main {
  public static void main(String[] args) throws Exception {
    
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

    int n = Integer.parseInt(br.readLine());

    long num = 1;
    int cnt = 0;

    for (int i = 1; i <= n; i++) {
      num *= i;
    }

    String numStr = String.valueOf(num);

    for (int i = 0; i < numStr.length(); i++) {
      if (numStr.charAt(i) == '0') {
        cnt++;
      }
    }

    bw.write(String.valueOf(cnt));
    bw.newLine();
    bw.flush();
    bw.close();
  }
}

 

ㄴ int 타입이었던 num을 long 타입으로 변경하여 디버깅 시 제대로 출력됐지만 채점 시 틀림을 확인하였다.

 

 

 

세 번째 작성한 코드

import java.io.*;
// import java.util.*;

public class Main {
  public static void main(String[] args) throws Exception {

    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

    int n = Integer.parseInt(br.readLine());

    int cnt = countZerosInFactorial(n);

    bw.write(String.valueOf(cnt));
    bw.newLine();
    bw.flush();
    bw.close();
  }

  private static int countZerosInFactorial(int n) {
    int cnt = 0;

    // 2와 5의 개수 중 더 작은 것이 0의 개수를 결정한다.
    // 5의 개수가 더 적으므로 5의 개수 카운팅.
    for (int i = 5; i <= n; i *= 5) {
        cnt += n / i;
    }

    return cnt;
  }
}

 

ㄴ 팩토리얼 계산 후 결과를 문자열로 변환하여 0의 개수를 세는 방법은 비효율적임을 확인하여 팩토리얼을 계산하면서 2와 5의 갯수를 세는 방법을 사용하도록 함

=> 2 와 5를 곱하면 10이 되므로 이 두 쌍이 있는 경우가 0의 개수를 나타냄을 알 수 있다.

=> 그러므로 두 쌍이 생기는 경우인 2와 5 중 개수가 작은 수가 0의 개수를 의미함을 알 수 있다.

 

 

---

 

 

문제점 : 디버깅 시 정상 출력되지만 채점 시 틀렸다는 것을 확인하였다.

해결 방법 : 2와 5를 곱하면 10이 되는 것을 생각하여 이 두 쌍이 있는 경우가 0의 개수를 나타냄을 알 수 있었다.

깨달은 바 : 비효율적인 방법을 효율적인 방법으로 해결할 수 있도록 잘 생각해봐겠다.