문제출처: https://www.acmicpc.net/problem/2023
2023번: 신기한 소수
수빈이가 세상에서 가장 좋아하는 것은 소수이고, 취미는 소수를 가지고 노는 것이다. 요즘 수빈이가 가장 관심있어 하는 소수는 7331이다. 7331은 소수인데, 신기하게도 733도 소수이고, 73도 소수
www.acmicpc.net
문제 이해
목표
자릿수 N이 주어졌을 때 가장 높은 자릿수부터, 한 개, 두 개, 세 개... N개의 정수가 모두 소수가 되는 신기한 소수를 만드는 것이다. ex) 7331 -> 7 소수, 73 소수, 733 소수, 7331 소수
풀이
-> 1의 자릿수부터 시작해서 ~ N자릿수로 구성된 순열을 만들 것이다.
ex) 7331을 만들기위해 7 검사, 73 검사, 733 검사, 7331 검사하도록 1의 자릿수부터 4의 자릿수까지의 순열을 만든다.
(순열을 구성하는 숫자는 1~9까지 모두로 하면 시간복잡도가 높기 때문에 소수가 나올 수 없는 숫자들은 제외하고 순열을 만들 것이다.)
-> 각 자릿수마다 완성된 순열은 소수인지 검사를 받는다.
검사 방법: 해당 순열을 (2 ~ 순열의 반값 + 1) 까지로 나누어 본다.
한 번이라도 나머지가 0이면 나누어 떨어지는 것이므로 이 순열은 소수가 아니다. 만약 아니라면 소수다.
소스코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
public class Main {
private static int N;
private static int[] intArr;
private static ArrayList<Integer> answerArr;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
N = Integer.parseInt(br.readLine());
intArr = new int[N]; // N 자리수 순열을 만들 배열
answerArr = new ArrayList<>();
int[] initArr = {2, 3, 5, 7}; // 첫 자리수
int[] nextArr = {1, 3, 7, 9}; // 다음에 올 자릿수 중 가장 소수의 가능성이 있는값들
if (N == 1) {
for (int i : initArr) { // N==1이면 initArr이 정답
answerArr.add(i);
}
} else {
for (int i = 0; i < 4; i++) {
intArr[0] = initArr[i];
getPermutation(1, nextArr);
}
}
for (Integer answer : answerArr) {
System.out.println(answer);
}
}
private static void getPermutation(int start, int[] nextArr) {
for (int i = 0; i < 4; i++) {
intArr[start] = nextArr[i]; // 다음자릿수에 값 넣음
int nowInt = 0; // 다음 자릿수를 넣고나서 완성된 값(다음값)
for (int j = start, k = 0; j >= 0; j--,k++) { // 순열-> 정수로 변환
nowInt += Math.pow(10, j) * intArr[k];
}
// 다음값이 소수 인지 검사
int half = (nowInt / 2) + 1;
boolean sosuCheck = true;
for (int j = 2; j <= half; j++) {
if (nowInt % j == 0) {
sosuCheck = false;
break;
}
}
if (sosuCheck) { // 소수 이면 다음 자릿수의 순열을 채우러 재귀
if (start + 1 == N) {
answerArr.add(nowInt);
continue;
}
getPermutation(start + 1, nextArr); // 다음자리 채우러 출발
}
}
}
}initArr: N자리 소수를 만들 대 첫 번째 값이 될 수 있는 후보들. (2, 3, 5 , 7은 소수이다)
nextArr: 첫 번째 자리가 아닌 다음 자리에 올 수 있는 후보들 (1, 3, 7, 9)
(2,4,5,6,8은 모두 마지막 자리에 왔을 때 해당 값이 소수가 아니도록 만든다 따라서 순열로 만들 때 배제해도 된다)
getPermutation: 소수를 검사하면서 순열을 만들음. 자릿수가 N개로 완성됐을 때는 정답 리스트에 넣고 재귀를 반복 안 한다.
개선 전략
- 소수 구하기 (소수인지 확인하기)
소수를 구하기 위해 2부터 ~ 해당 값의 반값까지로 나눠봤었다. 하지만 반 값이 아닌 제곱근으로 해도 된다고 한다.
제곱근은 가질 수 있는 몫의 최댓값이고, 그 이상의 값들은 제곱근 이하의 값들과 곱해서 구해지기 때문에, 최대 몫인 제곱근까지만 검사해도 된다! (제곱근 이상의 값들은 제곱근 아래의 수들과의 곱이기 때문에 알아서 걸러짐)
제곱근으로 바꾸고 검사 속도 차이 - 순열을 구할 때, 배열로 구하는 것 vs String으로 구하는것
String으로 구한 풀이가 있어서 더 편하겠다 싶어서(순열 -> 정수 변환을 parsing만 하면되기 때문) 확인을 해보았지만, 역시나 더 오래걸리고 메모리도 많이 잡아 먹는 것을 확인할 수 있었다. 순열을 구할땐 배열로 구하는게 나을 것 같다.