🙋 재귀함수(DFS) + 자릿수 개념 + 가지치기
문제분석
DFS는 재귀함수의 형태를 띄고있다!
재귀함수를 사용해야할 것 같으므로 DFS를 이용하는것이다.
재귀함수에 자릿수 개념을 붙여 구현한다.
문제 조건에 맞도록 가지치기도 한다.
처음에 내가 생각한대로 한건 결국 틀리기도했고, 스터디 팀원이 나와 같은로직으로 예제 답과 맞게 나왔는데, 백준에서 시간초과가 났다.
이하 해당 내용이다.
슈도코드
N 입력받기
int number = 1*10^N
for(i : number ~ 1*10^(N+1)-1) {
int index = N-1
boolean few = Few(i)
while(few) {
String strNumber = String.valueOf(i)
strNumber.substring(0,index)
nextNumber = Integer.parseInt(strNumber)
few = Few(nextNumber)
index--
if(index == 0) {
i 출력
}
}
i++
}
// 소수확인
public static boolean Few(int num, N) {
boolean few = true
for(i : 2~N-1 만큼 반복) {
int remainder = n%i
if( remainder == 0) {
few = false
return few
}
}
return few
}Troubleshooting
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int N = sc.nextInt();
int number = 1*10^N;
int lastNumber = 1*10^(N+1)-1;
for(int i = number; i <= lastNumber ; i++) {
int index = N-1;
boolean few = Few(i, N);
while(few && index > 0) {
String strNumber = String.valueOf(i);
strNumber.substring(0,index);
int nextNumber = Integer.parseInt(strNumber);
few = Few(nextNumber, N);
index--;
if(index == 0) {
System.out.println(i);
break;
}
}
i++;
}
}
public static boolean Few(int num, int N) {
boolean few = true;
for(int i =2; i < N; i++) {
int remainder = num%i;
if(remainder == 0) {
few = false;
return few;
}
}
return few;
}
}문제
예제에 나오는 4를 입력했을 때, 아무런 결과가 나오지않는다.
이 때, 스터디를 하면서 다른 분도 나와 같은 로직(4자리수인경우 1000~9999까지 차례대로 모두 판단하는 로직)을 사용하셨는데, 답은 나왔지만 백준에서 시간초과가 났다.
따라서 이 로직은 분석하지않고, 버리기로..!
시간복잡도
N의 최대가 8이다.
해당 로직으로 할 경우, 가장 첫번째 자리에는 1~9, 그 이하 7자리에는 0~9가 올 수 있으므로 가능한 경우의 수는 910^7이다.
이 경우 각 숫자에 대해 자릿수를 하나씩 줄이기 때문에 한 숫자당 총 8개가 나오므로
(910^7)*8이라 벌써 2억이 넘어가는데, 여기에 각 숫자가 소수인지 판별하는 소수 시간복잡도까지 곱해지면.. 시간제한인 2초내에는 확실히 안될것으로 보인다
그래서 잘 알려진 방법을 찾아봤다.
접근방법
우선 자릿수가 한 개인 소수를 살펴보자 : 2,3,5,7 -> 이 수부터 탐색을 시작한다.
즉, 4,6,8,9를 제외하는 가지치기 방식을 적용한 것
이어서 자릿수가 두 개인 현재 수 * 10 + a를 계산해 이 수가 소수인지 판단하고, 소수라면 재귀 함수로 자릿수를 하나 늘린다.
단, a가 짝수인 경우는 항상 2를 약수를 가지므로 가지치기로 a가 짝수인 경우는 제외한다.
이런 방식으로 자릿수를 N까지 확장했을 때 그 값이 소수라면 해당 값을 출력한다.
->DFS로 탐색하지만, 첫 탐색 배열, 중간 탐색 배열을 가지치기하여 시간 복잡도를 줄인다. 또한 중간 탐색과정에서 소수가 아닌 경우 멈추는 가지치기도 포함이므로 시간 복잡도가 더 줄어들것이다.
(반대로도 생각할 줄 알아야하는구나..
사실 문제를 자세히보면 '즉, 왼쪽부터 1자리, 2자리, 3자리, 4자리 수 모두 소수이다!'라는 말이있다. 이게 힌트가 될 수 있을것같다. 문제를 자세히 분석하자!!)
슈도코드
다시 짜보자
N 입력받기
DFS {
if(자릿수 == N) {
if(소수) 수 출력
DFS 종료
}
for(1~9 반복) {
if(뒤에 붙는 수가 홀수이면서, 전체 수가 소수) {
DFS : 자릿수+1, 수*10+뒤에 붙는 수
}
}
}
//소수 구하기
for(i : 2~ '현재수 / 2' 반복) {
if(수 % i ==0) return 소수아님
}
return 소수Troubleshooting
import java.util.Scanner;
public class Main {
static int digit =1;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int N = sc.nextInt();
DFS(2,N);
DFS(3,N);
DFS(5,N);
DFS(7,N);
}
public static void DFS(int number, int N) {
if((int)(Math.log10(number) +1) == N) {
System.out.println(number);
return;
}
for(int i = 1; i<10; i = i+2) {
number = number*10 + i;
if(!checkPrimeNumber(number)) return;
DFS(number, N);
}
}
public static boolean checkPrimeNumber(int number) {
boolean isPrime = true;
for(int j=2; j<=number/2; j++) {
if(number%j == 0) {
isPrime = false;
break;
}
}
return isPrime;
}
}문제
예제 4를 넣었을 때, 아무값이 나오지않는다.
원인
숫자의 자릿수구하는게 헷갈려서 찾아보고 진행했는데, 그 문제인가싶었다.
해결
그때그떄 자릿수를 구하기위해 (int)(Math.log10(number) +1)를 digit변수를 이용하도록 수정했다.
Troubleshooting 2
import java.util.Scanner;
public class Main {
static int N;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
N = sc.nextInt();
DFS(2,1);
DFS(3,1);
DFS(5,1);
DFS(7,1);
}
public static void DFS(int number, int digit) {
if(digit== N) {
if(checkPrimeNumber(number)) {
System.out.println(number);
}
return;
}
for(int i = 1; i<10; i = i+2) {
number = number*10 + i; // 이렇게하면 안된다.
if(checkPrimeNumber(number)) { // number 매개변수 틀림
DFS(number, digit+1); //number 매개변수 틀림
}
}
}
public static boolean checkPrimeNumber(int number) {
boolean isPrime = true;
for(int j=2; j<=number/2; j++) {
if(number%j == 0) {
isPrime = false;
//break;
}
}
return isPrime;
}
}문제
4를 넣었을때 위와같이 결과가 이상하게 나온다.
원인
결과가 4개이고 각각 절댓값이 엄청 큰 수인것을 봤을때, DFS의 매개변수인 number이 누적된것같다.
(반복문에서 항상 변수사용 실수가 반복됐던것같다...)
예를들어, 정상적으로는 처음에 (2,1)이 들어갔을 때 number은 21이되고, 소수가아니므로 끝나야한다.
하지만, for문안에서 변수에 계산 결과를 대입해서 계속 반복해서. 즉 number = number*10 + i;로 인해 21 -> 213->2135->21357->... 이런식으로 소수가 아닌수인데 해당 수로 계속 반복문을 돈다.
해결
for문 안에서 소수일때만 재귀호출하고, 소수가 아닐때에는 다시 그 전 number에 그 다음 루프로 넘어가야하기때문에 number를 갱신하는식으로 코딩하면안된다.
파라미터에 number써야할때, 필요한 계산식을 넣어주자! 파라미터로 들어오는 값이든 for문안에서 파라미터로 사용되는 값이든 함부로 갱신하면안된다.
제출코드
import java.util.Scanner;
public class Main {
static int N;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
N = sc.nextInt();
DFS(2,1);
DFS(3,1);
DFS(5,1);
DFS(7,1);
}
public static void DFS(int number, int digit) {
if(digit== N) {
if(checkPrimeNumber(number)) {
System.out.println(number);
}
return;
}
for(int i = 1; i<10; i = i+2) {
if(checkPrimeNumber(number*10 + i)) {
DFS(number*10 + i, digit+1);
}
}
}
public static boolean checkPrimeNumber(int number) {
boolean isPrime = true;
for(int j=2; j<=number/2; j++) {
if(number%j == 0) {
isPrime = false;
}
}
return isPrime;
}
}공부한 사항
- 소수판별 코드 : 2~(n/2)까지 절반만 체크하면된다.(계산횟수 줄임)
