[JAVA] 3474 - 교수가 된 현우 🩶3 : 시간복잡도가 위험할 땐 모듈러 다음으론 제곱수를 생각하자.

들어가며

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

문제를 요약하자면, N이라는 숫자에 대해 팩토리얼 연산을 진행했을때 오른쪽 끝에 있는 0의 개수를 구하는 것이였다. 

본론으로

처음에는 N의 최대 크기 10억정도되는 크기랑 절대 곱해서 저장하면 안되겠다.. 오버플로우 나겠다 싶었다. 그래서 곱하기 연산은 피하고, 하나씩 줄여가며 2와 5의 개수를 찾아서 최소개수를 출력하자! 라는 식으로 생각이 좁혀졌다. 아래는 처음 코드다

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(bf.readLine());

        for (int i = 0; i < T; i++) {
            int number = Integer.parseInt(bf.readLine());
            int twoCnt = 0;
            int fiveCnt = 0;
            int tenCnt = 0;
            for (int j = number; j >= 1; j--) {
                int checkNum = j;
                while (checkNum % 10 == 0 && checkNum > 9) {
                    checkNum /= 10;
                    tenCnt++;
                }
                while (checkNum % 5 == 0 && checkNum > 4) {
                    checkNum /= 5;
                    fiveCnt++;
                }
                while (checkNum % 2 == 0 && checkNum > 1) {
                    checkNum /= 2;
                    twoCnt++;
                }
            }

            System.out.println(Math.min(twoCnt, fiveCnt) + tenCnt);
        }
    }
}

---

하나씩 줄여가며 2와 5의 개수를 체크하는 위의 코드는 시간복잡도가 O(10억)이라 시간 초과가 난다. 그러면 어떻게 해야할까? 도저히 생각이 안나서 20!을 그림을 그려가며 생각해보았다.

글씨체는 부끄럽지만 숫자를 제곱수로 나눈다면 팩토리얼 안에 나눈 숫자가 몇개 들어가 있는지 알 수 있다는 사실을 알 수 있다. 즉 (N / 2 ^ 1) + (N / 2 ^ 2) + (N / 2 ^ 3) ... 식으로 2의 개수를 구할 수 있다. 그렇다면 5의배수도 마찬가지로 로직을 아래처럼 구현할 수 있다.

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(bf.readLine());

        for (int i = 0; i < T; i++) {
            int number = Integer.parseInt(bf.readLine());
            int twoCnt = 0;
            int fiveCnt = 0;
            for (int j = 2; j <= number; j *= 2) {
                twoCnt += number / j;
            }
            for (int k = 5; k <= number; k *= 5) {
                fiveCnt += number / k;
            }

            System.out.println(Math.min(twoCnt, fiveCnt));
        }
    }
}

마무리하며

여러 블로그를 찾아보니 5의 개수는 2의개수보다 절대적으로 작을 수밖에 없으니 5의 개수만 카운팅하시는 분들도 계셨다. 그래도 10의 개수를 구하는 이 로직이 조금 더 정답에 어울린다고 생각한다!! 

참.. 시간복잡도를 줄이기 위한 정수론 풀이들은 많은 연습들이 필요한 것 같다!