[문제 풀이] 백준 11653번 소인수분해 JAVA

문제

본 문제는 정수 N을 입력받았을 때 N의 소인수분해 결과를 출력하는 프로그램을 작성하는 문제이다.

처음 접근 방식은 입력받은 N을 2로 나누다가 나누어 떨어지지 않으면 3으로 증가시켜서 다시 나누는 방식을

반복하면 가능할 것 같아 그렇게 접근하였다. 처음에 시간초과가 나와서 당황했지만

조건문을 너무 어렵게 꼬아서 작성한게 문제였고 조건문을 수정하여 문제를 해결하였다.

 

< 초기 코드 >

import java.util.*;
public class Main
{
	public static void main(String args[]){
        Scanner s=new Scanner(System.in);
        int n=s.nextInt();
        
        primeFactorization(n);
    }
    public static void primeFactorization(int n){
        int i=2;
        while(true){
            if(n==1){break;}
            if(n%i==0){
                System.out.println(i); 
                n/=i;
                }
            else{i++;};
            
            
            
        }
    }
}

본 코드의 시간 복잡도는 O(N)으로 N이 최대 10,000,000 임으로 1초 안에 해결이 가능한 것을 확인해 볼 수 있다.

위의 코드도 좋지만 while문에서 조건을 if문으로 빼는 것과 출력할때마다 System.out.println()하는 부분을 

조금 더 효율적이게 수정하여 아래와 같은 코드를 작성하였다.

 

< 최종 코드 1 >

import java.util.Scanner;

public class Main{
    public static void main(String args[]){
        Scanner s=new Scanner(System.in);
        StringBuilder sb=new StringBuilder();
        int n=s.nextInt();
        int start=2;
        while(n!=1){
            if(n%start!=0){start++;}
            else{
                n=n/start;
                sb.append(start+"\n");
            }
            
        }
        System.out.print(sb);
    }
}

해당 코드처럼 StringBuilder을 활용해 출력을 모았다가 한번에 호출로 출력하게 함으로써 성능과 효율을 초기코드보다

높일 수 있게 되는 것이다.  

초기코드와 최종코드 모두 start를 설정하고 while문에서 조건으로 나누어서 진행하였지만 아래와 같이 for문으로 대체도 가능하다.

 

< 최종 코드 2 >

import java.util.Scanner;

public class Main{
    public static void main(String args[]){
        Scanner s=new Scanner(System.in);
        StringBuilder sb=new StringBuilder();
        int n=s.nextInt();
        for(int i=2;i<=n;i++){
            while(n%i==0){
                n=n/i;
                sb.append(i+"\n"); 
            }
        }
        System.out.print(sb);
    }
}

소인수분해라는 것이 입력받은 N인 자신보다 큰 숫자가 존재하는 것은 불가능하므로 최소 숫자인 2부터 N까지 중에서

조건에 맞는다면 while문에서 나눗셈을 진행하고 StringBuilder에 저장해두었다가 출력하는 방식이다.

 

 

< 최종 코드 3 ver 에라토스테네스의 체 기반 소인수분해 >

import java.util.*;

public class Main{
    public static void main(String args[]){
        Scanner s=new Scanner(System.in);
        StringBuilder sb=new StringBuilder();
        int n=s.nextInt();
        int limit = (int)Math.sqrt(n) + 1;
        boolean prime[]=new boolean[limit+1];
        primeTool(prime);
        
        for(int i=2;i<prime.length;i++){
            while(n%i==0&&prime[i]){
                n=n/i;
                sb.append(i+"\n"); 
            }
        }
        if (n > 1) sb.append(n).append("\n");
        System.out.print(sb);
        
        
    }
    public static void primeTool(boolean prime[]){
        Arrays.fill(prime,true);
        prime[0]=prime[1]=false;
        for(int i=2;i<prime.length;i++){
            if(prime[i]){
                for(int j=i*i;j<prime.length;j+=i){
                    prime[j]=false;
                }
            }
        }
    }
}

해당 문제는 에라토스테네스의 체를 이용가능하긴하지만 굉장히 과한 방식이고 조건이 많이 붙는다.

먼저 처음에는 boolean 배열의 크기를  n+1로 생성했지만 이는 메모리 초과를 발생시켰다.

이론상으로는 문제가 없어 보이지만 실제로는 자바에서 제출 환경 힙 크기 제한 때문에 메모리 초과로 런타임 에러 발생 가능하며 특히 백준에서는 JVM 힙 사이즈가 제한되어 있어 더 그럴 확률이 높다고 한다.

그래서 제곱근까지만 배열을 생성하는 방식으로 문제를 해결하고자 했지만 또다른 문제가 발생했다.

n = 9999991일 경우에 √9999991 ≈ 3162 → 소수는 3163 이상이어야한다. 하지만 prime[]에는 3163이 없다.

즉 나눌 수 있는 소수가 없으니 아무것도 출력되지 않는다. 그래서 위의 메모리도 해결했지만 틀렸다는 판정을 받은 것 이다.

그래서 마지막 줄에 조건문을 통해 모든 과정을 거쳤는데도 1이상이라면 추가해주는 식을 추가해 맞았다는 결과를 얻었다.

결론적으로 해당 문제에서는 적절하지 못한 방법인것같다.