[G5] 신기한 소수 찾기 : Java : 2023 - DFS

문제

2023번: 신기한 소수

 

 

풀이 방법

신기한 소수가 되기 위해서는 왼쪽부터 1자리, 2자리, 3자리, 4자리 모두 소수여야 한다. 즉 1자리 부터 소수가 아니면 검사할 필요가 없기에 점점 깊이 파고 드는 재귀함수를 써야 한다고 생각 헀다.  => DFS가 적당!

 

재귀 함수의 깊이가 입력 받은 자릿수가 되면 그 수는 신기한 소수이다.

내가 생각한 알고리즘은 밑과 같았다.

1. 1~9까지 i가 소수이면 findInterestDemical 함수를 호출한다. 인자는 num과 자릿수. 자릿수는 현재 1 => 1자리 소수 찾기

2. findInterestDemical 함수에서 1~9까지 루프를 돈다

	2.1 num과 j를 합쳤을 때 소수라면 합친 수를 인자로 findInterestDemical 함수를 호출 한다. 자릿수는 현재  2 => 2자리 소수 찾기
	2.2 만약 호출한 자릿수와 입력받은 자릿수가 같다면 해당 수는 신기한 소수로 출력한다.

 

알고리즘을 코드로 옮기면서 점점 추가되는 num을 ArrayList로 표현하면 더 쉬울까 생각했다. 그래서 각 자리수에 해당하는 값을 add해서 인자로 넘겨줬는데 오히려 훨씬 혼란스러웠다. 2가지 문제가 있었다. 그래서 답 코드를 보고 바로 int로 고쳤다...

1. 객체여서 재귀함수로 다른 값으로 함수를 호출하여도 같은 주소를 참고하기 때문에 값이 바뀌지 않음
2. 자릿수만 빼서 10을 거듭제곱해서 하나의 수롤 통합하는게 오래 걸림

최종은 메모리 초과로 풀지 못했다. 그래서 해답 코드를 보면서 내 코드와 비교해봤다. 또 다른 문제는 함수에서 같은 객체를 참고하기 때문에 값을 변경하고 호출한 다음, 함수를 실행하고 돌아오면 변경된 값 그대로 였다. 그래서 돌아온 다음 다시 값을 변경해줘야 했는데 이 부분에서 내 예상대로 값이 변경 되지 않았다. 그래서 깨달은 것은 변수에 바뀐 값을 반영하지 않고 함수를 호출할 때 바로 원하는 값으로 호출하는 것! 이해하기 어려우니 코드로.. . 보기엔 똑같이 보이지만 다루기가 더 힘들다. 이제부터 함수를 호출할 때는 직접적인 변경보다는 연산한 값으로 호출하는걸로! 

// 내가 썼던 방법
if(isPrime(num*10 + i)){
	  num = num + i;
      findInterstingDecimal(count+1, num);
      num = num - i;
 }


// 좋은 방법
 if(isPrime(num*10 + i)){
      findInterstingDecimal(count+1, num + i);
 }

 

 

 

코드 - Java

import java.io.*;
import java.util.ArrayList;
import java.util.Scanner;
import java.util.StringTokenizer;


public class Main {

    static int disit;
    public static void main(String [] args) throws IOException{
        Scanner sc= new Scanner(System.in);
        disit = sc.nextInt();
        int max = 0;
        for(int i=1; i<disit+1; i++){
            int disit_num = 9;
            for(int j=1; j<i;j++)
                disit_num*=10;
            max += disit_num;
        }

        for(int i=2; i<=9; i++){
            // 소수
            if(isPrime(i)){
                findInterstingDecimal(1, i);
            }
        }


    }

    static boolean isPrime(int num){
        for(int i =2; i<=num/2; i++){
            if(num % i ==0)
                return false;
        }
        return true;
    }

    static void findInterstingDecimal(int count,int num){
        //count++;
        if(count == disit){
            if(isPrime(num)){
                System.out.println(num);
            }
            return;
        }

        for(int i=1; i<=9; i++){
            if(i % 2 == 0)
                continue;
            if(isPrime(num*10 + i)){
                findInterstingDecimal(count+1, num*10 + i);
            }
        }
    }


}