백준 문제 풀이 - 약수, 배수와 소수 단계 - 11653번 소인수분해 (브론즈 1)

정수 N이 주어졌을 때, 소인수 분해하는 프로그램을 작성하는 간단한 문제이다.

우선 소인수분해에 대해서 알아보자.

 

소인수분해는 어떤 자연수를 소수의 곱으로 분해하는 과정을 말한다.

간단히 말하자면, 주어진 수를 더 이상 분해할 수 없을 때까지 소수로 나누어주는 과정이다.

 

따라서 이번 문제는, 얼마나 빠르게 소수를 찾아 가장 작은수 부터 출력해 주느냐가 관건이 되겠다.

나는 이전 문제부터 사용하던 소수 판별 로직을 가져와, 가장 작은 소수부터 잘라 나가는 코드를 만들었다.

import java.io.*;

class Main{
    public static int n,num;
    public static boolean isPrime;
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        n = Integer.parseInt(br.readLine());
        br.close();
        num = 2;
        
        while(n>0){
            if(checkPrime(num) && n % num ==0){
                System.out.println(num);
                n /= num;
            } else{
                num++;
            }
        }
        
    }
    
    public static boolean checkPrime(int n){
        for(int i = 2; i*i <= n; i++){
            if(n % i == 0){
                return false;
            }
        }
        return true;
    }
}

코드를 살펴보면 checkPrime() 이라는 메서드를 만들어 int 값을 던지고 해당 값이 소수인지 for 문으로 판별하여 boolean 타입으로 리턴한다.

그리고 만일 던져진 값이 소수이고, 주어진 값 n이 소수로 나누어지면 해당 소수를 출력하고 n을 소수로 나누면서 0보다 작아질때까지 반복하는 로직이다.

 

그런데 실제로 코드를 제출해보니 시간이 초과되는 것을 확인 할 수 있었다.

따라서 보다 빠르게 소수를 계산할 필요성이 있어 일반적으로 사용하는 에라스토테네스의 체 알고리즘을 사용하기로 하였다.

에라토스테네스의 체 알고리즘의 원리는 다음과 같다.

1. 초기화: 2부터 시작해서 N까지의 모든 수를 나열합니다.
2. 소수 찾기: 현재 숫자의 배수들을 제외시킵니다.
3. 다음 숫자로 이동: 다음으로 남아있는 수를 선택하고, 그 수의 배수들을 제외시킵니다.
4. 반복: 위 과정을 끝까지 반복하면, 남아있는 수가 소수가 됩니다.

그렇다면 실제로 적용된 예시 코드를 살펴보자.

여기서는 1~100까지의 범위에서 소수를 구하는 것으로 가정한다.

import java.util.*;

public class SieveOfEratosthenes {
    public static void main(String[] args) {
        int n = 100;
        boolean[] isPrime = new boolean[n + 1];
        Arrays.fill(isPrime, true);

        // 0과 1은 소수가 아님
        isPrime[0] = false;
        isPrime[1] = false;

        // 에라토스테네스의 체 알고리즘 적용
        for (int i = 2; i * i <= n; i++) {
            if (isPrime[i]) {
                for (int j = i * i; j <= n; j += i) {
                    isPrime[j] = false;
                }
            }
        }

        // 소수 출력
        for (int i = 2; i <= n; i++) {
            if (isPrime[i]) {
                System.out.print(i + " ");
            }
        }
    }
}

위 코드를 살펴보면 우선 0~100까지의 배열을 만들고(여기서는 boolean 타입을 사용하지만 int 배열로도 사용 가능하다), 배열의 0,1을 제외한 모든 값을 true로 채운다. 그 후, 입력된 최대 값(100)까지 반복하며, 해당 값이 소수라면 소수의 모든 배수를 false 처리한다.

이렇게 하면 모든 범위의 반복을 할 필요없이 빠르게 소수 처리가 가능한데, 단점은 배열을 만들어 사용하므로 너무 넒은 범위가 주어지면 메모리의 문제가 생길 수 있으니 주의하자.

 

따라서, 나는 내 코드를 다음과 같이 수정하였다.

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

class Main{
    public static int n,num;
    public static boolean isPrime;
    public static boolean[] prime;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        n = Integer.parseInt(br.readLine());
        br.close();
        prime = new boolean[n+1];
        Arrays.fill(prime,true);
        prime[0] = false;
        prime[1] = false;
        prime = getPrime(prime,n);
        num = 2;

        while(n>1){
            if(prime[num] && n % num == 0){
                System.out.println(num);
                n /= num;
            } else {
                num++;
            }
        }

    }

    public static boolean[] getPrime(boolean[] prime,int n){
        for(int i = 2; i*i <= n; i++){
            if(prime[i]){
                for(int j = i * i; j <= n; j+=i){
                    prime[j] = false;
                }
            }
        }
        return prime;
    }
}

코드를 살펴보면 getPrime이란 메서드를 이용하여 소수만을 담은 boolean 배열을 리턴한다.

그리고 n이 1보다 클때까지 반복하며 소수로 나눠지는 경우 출력한다.

위와 같이 처리하여 문제를 풀수 있었다.

 

그런데 다른 사람의 코드를 살펴 보던 중, 훨씬 간단하게 구현된 코드를 발견하였다.

import java.util.Scanner;

public class Main {
    public static void main(String args[]) {
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        if(n != 1) {
            for(int i=2; i<=n; i++) {
                while(n % i == 0) {
                    System.out.println(i);
                    n = n/i;
                }
            }
        }
    }
}

잘 생각해 보면 이 문제는 굳이 소수를 구할 필요가 없다.

어차피 2부터 나누어가면 해당 숫자의 배수로 나누기 전에 가장 작은 수부터 출력이 되기 때문이다.

따라서 2부터 반복하며 주어진 값 n이 나누어 떨어지지 않을때 까지 반복하다가 나누어 떨어지지 않으면 다음 숫자로 나누어주면 된다.

알고리즘에 집중하다 보니 문제를 너무 어렵게 생각했는데 좀더 간단한 방법이 많으니 알고리즘에 너무 집중하지 않도록 주의해야 할 것같다.