[백준] 11653 : 소인수분해

문제 출처: https://www.acmicpc.net/problem/11653

11653번: 소인수분해

---

1. 문제

문제

정수 N이 주어졌을 때, 소인수분해하는 프로그램을 작성하시오.

입력

첫째 줄에 정수 N (1 ≤ N ≤ 10,000,000)이 주어진다.

출력

N의 소인수분해 결과를 한 줄에 하나씩 오름차순으로 출력한다. N이 1인 경우 아무것도 출력하지 않는다.

 

---

2. 시도

 

가장 무난하게 for문을 2부터(1은 소인수분해 값이 될 수 없으므로) 입력인 N까지 반복하도록 코드를 작성했다.

 

import java.io.*;

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

        // input : n (1 <= N <= 10,000,000)
        int n = Integer.parseInt(br.readLine());
        if(n == 1) return;

        for(int i = 2; i <= n; i++) {
            while (n % i == 0) {
                sb.append(i + "\n");
                n /= i;
            }
        }

        System.out.println(sb);
    }
}

 

정답이었다. Java 8 환경에서 총 120ms 소요되는 것을 확인했다.

 

다만 이제는 풀었다고 끝내는 것이 아니라 알고리즘에 대한 이해를 가지고 더 나은 방법을 찾기 위해 노력해야 할 시기란 걸 알기 때문에 개선된 코드를 찾아 다른 정답자들의 코드를 찾았다.

---

3. 해결

 

Java 8 제출자들 중 가장 빠른 해결 속도를 보인 풀이들을 참고하니 문제를 푼다는 것에서 더 나아가 문제를 이해하고 있다는 것이 확실히 느껴졌다.

그들은  '소인수분해'라는 문제 주제에 집중하여 주어진 수 N을 소수로 나눈다는 점에 집중해 다음의 사실을 적용했다.

 

어떤 N이 두 개이상 곱셈(인수)으로 나타낼 수 있을 때 인수 중 한 개 이상은 반드시 √N보다 작거나 같다

 

i) 반복문의 경우를 i * i <= N으로 바꾼 경우 

import java.io.*;

public class Main {
	public static void main(String[] args) throws NumberFormatException, IOException {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine());
		StringBuilder sb = new StringBuilder();
		
		for(int i = 2; i*i<=n; i++) {
			while(n%i == 0) {
				sb.append(i).append('\n');
				n /= i;
			}
		}
		if(n != 1) {
			sb.append(n);
		}
		
		System.out.println(sb);
		
	}

}

 

ii) 반복문의 범위를 루트 N으로 감축한 경우

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
 
public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
 
		StringBuilder sb = new StringBuilder();
		int N = Integer.parseInt(br.readLine());
 
		for (int i = 2; i <= Math.sqrt(N); i++) {
			while (N % i == 0) {
				sb.append(i).append('\n');
				N /= i;
			}
		}
		if (N != 1) {
			sb.append(N);
		}
		System.out.println(sb);
	}
}

 

참고 출처

 - https://www.acmicpc.net/source/5161197

 - https://st-lab.tistory.com/152

---

4. 알게 된 점

 

정확히 푸는 것도 중요하지만 현재 내게 필요한 건 더 많은 문제 풀이를 통한 경험 축적이라고 판단되는 문제였다.