[백준] 11653번 : 소인수분해 - JAVA [자바]

www.acmicpc.net/problem/11653

11653번: 소인수분해

 

---

• 문제

 

 

 

말 그대로 소인수분해를 하는 문제라 쉽게 풀 수 있을 것이다.

 

 

 

 

 

 

 

 

 

---

• 알고리즘 [접근 방법]

 

소인수분해. 영어로 prime factorization이라고 한다.

아마 대부분 우리나라 교육과정을 다 마치셨다면 기억하실 것이다. 말 그대로 어떤 수를 더이상 쪼개지지 않는 수들의 곱으로 분해하는 것이다.

이를 약간 변형해서 말하자면 어떤 정수 N을 소수들의 곱으로 나타낸다는 것이다.

 

위 문제에서는 

즉, 다음과 같은 구조로 짜면 된다.

 

/*
 * 임의의 정수 N에 대하여 곱셈으로 분해하면
 * 제곱근(√N)을 기준으로 대칭이 된다.  
 * 예로들어 9에 대하여 곱으로 표현하면
 * 1 * 9, 3 * 3, 9 * 1 이런식으로 말이다.
 * 즉, i * i 가 N 이하일 때 까지만 탐색해도 된다.
 */
for (int i = 2; i * i <= N; i++) {
	while (N % i == 0) {
		print(i + "\n");
		N /= i;
	}	
}
		
/*
 * 대신 제곱근까지만 탐색하면 나머지가 발생 할 수 있다.
 * 이 나머지는 1 또는 소수이고 반드시 1개임이 보장된다.
 * 예로들어 6의 경우 2는 저장되지만, 3은 앞의 for문에서 걸러지지 않는다.
 * 이런 경우에 대해 1이 아닐 경우에는 한 번 더 추가해주어야 한다.
 * 다른 경우에도 1개임이 보장되는 이유는, 해당 소수는 N의 제곱근 보다
 * 크다는 의미고, 그 소수로 나눠진 수는 N의 제곱근보다 항상 작기 때문에	
 * 작은 수 들은 앞선 for문에서 이미 걸러지게 되고, 나머지는 유일한 소수가 된다.
 */
if (N != 1) {
	print(N);
}

 

 

그리고 물론 N까지 모두 탐색하여 소인수분해를 구할 수도 있지만 이러한 방식은 누구나 다 할 것이고, 이번에는 조금 다르게 풀이하고자 한다. 바로 N의 제곱근까지만 탐색해주는 방식이다.

 

근데, 문제는 왜 if(N != 1)일 때 N을 한 번 더 출력해야하는지 모르는 분들이 많은 것 같아 주석으로 달아두었다.

 

 

 

 

 

 

 

 

 

 

 

---

• 2가지 방법을 사용하여 풀이한다.

 

이전 포스팅과 여타 다를 바 없이 아래와 같이 2가지 입력 방법을 통해 성능을 비교해보려 한다.

이번에는 출력을 모두 StringBuilder 로 통일하여 입력방법만 달리하여 풀이하겠다.

 

1 . Scanner + StringBuilder

2. BufferedReader + StringBuilder

 

 

 

 

---

• 풀이

- 방법 1 : [Scanner + StringBuilder]

 

import java.util.Scanner;

public class Main {

	public static void main(String[] args) {

		Scanner in = new Scanner(System.in);

		int N = in.nextInt();

		StringBuilder sb = new StringBuilder();

		/*
		 * 임의의 정수 N에 대하여 곱셈으로 분해하면
		 * 제곱근(√N)을 기준으로 대칭이 된다. 
		 * 예로들어 9에 대하여 곱으로 표현하면
		 * 1 * 9, 3 * 3, 9 * 1 이런식으로 말이다.
		 * 즉, i * i 가 N 이하일 때 까지만 탐색해도 된다.
		 */
		for (int i = 2; i * i <= N; i++) {
			while (N % i == 0) {
				sb.append(i).append('\n');
				N /= i;
			}
		}
		
		/*
		 * 대신 제곱근까지만 탐색하면 나머지가 발생 할 수 있다.
		 * 이 나머지는 1 또는 소수이고 반드시 1개임이 보장된다.
		 * 예로들어 6의 경우 2는 저장되지만, 3은 앞의 for문에서 걸러지지 않는다.
		 * 이런 경우에 대해 1이 아닐 경우에는 한 번 더 추가해주어야 한다.
		 * 다른 경우에도 1개임이 보장되는 이유는, 해당 소수는 N의 제곱근 보다
		 * 크다는 의미고, 그 소수로 나눠진 수는 N의 제곱근보다 항상 작기 때문에
		 * 작은 수 들은 앞선 for문에서 이미 걸러지게 되고, 나머지는 유일한 소수가 된다.
		 */
		if (N != 1) {
			sb.append(N);
		}
		System.out.println(sb);
	}
}

 

 

가장 기본적인 방법이라 할 수 있겠다.

 

워낙 쉬운 문제라 정답비율도 높은 것 같다. StringBuilder 대신 BufferedWriter를 써도 된다.

 

 

---

- 방법 2 : [BufferedReader + StringBuilder]

 

 

 

입력 방법을 Scanner 대신 BufferedReader 을 사용하여 풀이하는 방법이다. 단, BufferedReader 는 문자열을 한 줄로 읽기 때문에 N과 M을 구분하기 위해 공백을 기준으로 문자열을 분리해주어야하니 StringTokenizer 을 사용하여 풀도록 하겠다.

 

 

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));

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

		StringBuilder sb = new StringBuilder();

		/*
		 * 임의의 정수 N에 대하여 곱셈으로 분해하면
		 * 제곱근(√N)을 기준으로 대칭이 된다. 
		 * 예로들어 9에 대하여 곱으로 표현하면
		 * 1 * 9, 3 * 3, 9 * 1 이런식으로 말이다.
		 * 즉, i * i 가 N 이하일 때 까지만 탐색해도 된다.
		 */
		for (int i = 2; i * i <= N; i++) {
			while (N % i == 0) {
				sb.append(i).append('\n');
				N /= i;
			}
		}
		
		/*
		 * 대신 제곱근까지만 탐색하면 나머지가 발생 할 수 있다.
		 * 이 나머지는 1 또는 소수이고 반드시 1개임이 보장된다.
		 * 예로들어 6의 경우 2는 저장되지만, 3은 앞의 for문에서 걸러지지 않는다.
		 * 이런 경우에 대해 1이 아닐 경우에는 한 번 더 추가해주어야 한다.
		 * 다른 경우에도 1개임이 보장되는 이유는, 해당 소수는 N의 제곱근 보다
		 * 크다는 의미고, 그 소수로 나눠진 수는 N의 제곱근보다 항상 작기 때문에
		 * 작은 수 들은 앞선 for문에서 이미 걸러지게 되고, 나머지는 유일한 소수가 된다.
		 */
		if (N != 1) {
			sb.append(N);
		}
		System.out.println(sb);
	}
}

 

 

 

크게 어려울 것은 없을 것이다. 이번 문제는 중복을 고려하지 않아도 되니 오히려 쉬웠을 수도 있다.

 

 

 

 

 

 

 

 

 

 

---

• 성능

 

 

채점 번호 : 24852072  -  방법 2 : BufferedReader + StringBuilder

채점 번호 : 24852068  -  방법 1 : Scanner + StringBuilder

 

 

입력의 경우는 확실히 Scanner 보다는 BufferedReader 가 빠른 걸 볼 수 있다.

---

• 정리

 

이 번 문제 또한 어려운 점은 없었을 것이다. 

여담으로 두 소수의 곱을 하는 것은 쉽지만 역으로 두 소수의 곱으로 이루어진 어떤 수를 소인수분해를 하는 것은 매우 어렵다. 이 것을 이용한게 RSA같은 암호학의 가장 핵심적인 부분이 된다.

 

또한 필자가 탐색량을 N의 제곱근까지만 사용한 것도 대중적으로 많이 쓰이는 방식이지만, 정작 왜 그런지 고민을 하지 않고 푸는 경향도 의외로 많은 것 같다. 물론 필자가 왈가왈부 할 수는 없지만.. 그래도 한 번쯤은 고민을 해보고 풀어보는 것을 추천드린다.