[백준] 11653번 : 소인수분해 - JAVA [자바]
-
문제
말 그대로 소인수분해를 하는 문제라 쉽게 풀 수 있을 것이다.
- 알고리즘 [접근 방법]
소인수분해. 영어로 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의 제곱근까지만 사용한 것도 대중적으로 많이 쓰이는 방식이지만, 정작 왜 그런지 고민을 하지 않고 푸는 경향도 의외로 많은 것 같다. 물론 필자가 왈가왈부 할 수는 없지만.. 그래도 한 번쯤은 고민을 해보고 풀어보는 것을 추천드린다.
'JAVA - 백준 [BAEK JOON] > 기본 수학 2' 카테고리의 다른 글
[백준] 9020번 : 골드바흐의 추측 - JAVA [자바] (16) | 2020.05.05 |
---|---|
[백준] 4948번 : 베르트랑 공준 - JAVA [자바] (14) | 2020.04.24 |
[백준] 1929번 : 소수 구하기 - JAVA [자바] (18) | 2020.04.21 |
[백준] 2581번 : 소수 - JAVA [자바] (20) | 2020.04.21 |
[백준] 1978번 : 소수 찾기 - JAVA [자바] (20) | 2020.04.08 |