코딩 테스트 [탐색] - 신기한 소수 찾기

수빈이가 세상에서 제일 좋아하는 것은 소수이고, 취미는 소수를 이용해 노는 것이다. 요즘 수빈이가 가장 관심있어 하는 소수는 7331이다. 7331은 신기하게도 733도 소수, 73도 소수, 7도 소수다. 즉, 왼쪽부터 1자리, 2자리, 3자리, 4자릿수 모두 소수다. 수빈이는 이런 숫자를 신기한 소수라고 이름 붙였다. 수빈이는 N의 자리의 숫자 중 어떤 수들이 신기한 소수인지 궁금해졌다. 숫자 N이 주어졌을 때 N의 자리 숫자 중 신기한 소수를 모두 찾아보자.

(시간 제한 2초)

---

입력

1번째 줄에 N(1 ≤ N ≤ 8)이 주어진다.

출력

N의 자리 숫자 중 신기한 소수를 오름차순 정렬해 1줄에 1개씩 출력한다.

예제 입력
4  // 자릿수 N

예제 출력
2333
2339
2393
2399
2939
3119
3137
3733
3739
3793
3797
5939
7193
7331
7333
7393

---

1단계 - 문제 분석하기

DFS는 재귀 함수의 형태를 띄고 있다. 여기서는 재귀 함수의 원리를 이용해 DFS를 풀어보겠다.
이 문제는 재귀 함수에 자릿수 개념을 붙여 구현한다. 또한 문제 조건에 맞도록 가지치기도 하였다.

2단계 - 손으로 풀어 보기

소수는 약수가 1과 자기 자신인 수이다.

우선 자릿수가 한 개인 소수는 2, 3, 5, 7이므로 이 수부터 탐색을 시작한다. 4, 6, 8, 9를 제외한 가지치기 방식을 적용한것이다.
이어서 자릿수가 두 개인 현재 수 * 10 + a를 계산하여 이 수가 소수인지 판단하고, 소수라면 재귀 함수로 자릿수를 하나 늘린다. 단 a가 짝수인 경우는 항상 2를 약수로 가지므로 가지치기로 a가 짝수인 경우를 제외한다. 이런 방식으로 자릿수를 N까지 확장했을 때 그 값이 소수라면 해당 값을 출력한다.

위 그림을 보면 DFS의 형태로 탐색을 한다. 그리고 첫 탐색 배열, 중간 탐색 배열을 가지치기 하여 시간 복잡도를 줄였다. 또한 중간 탐색 과정에서 소수가 아닌 경우 멈추는 가지치기도 포함하여 더욱 시간 복잡도를 줄였다.
소수를 판별할때는 보통 에라토스테네스의 체를 사용하지만 여기서는 단순한 소수 판별 함수를 사용해도 시간 안에 문제를 풀 수 있다.

3단계 - sudo코드 작성하기

N(자릿수)

// DFS 실행
DFS(2,1)
DFS(3,1)
DFS(5,1)
DFS(7,1)

// DFS 구현
DFS(숫자, 자릿수) {
	if(자릿수 == N) {
    
    	if(소수)
        	수 출력
            
        탐색 종료
    }
    
    for(1 ~ 9) {
    	if(뒤에 붙는 수가 홀수이면서 소수일 때)
        	DFS(현재 수 * 10 + i, 자릿수 + 1)		// 자릿수를 1씩 늘리면서 DFS 실행
    }
}

// 소수 구하기 함수
isPrime(숫자){
	for(2 ~ 숫자/2){
    	if(나머지 == 0)
        	return 소수가 아님
    }
    return 소수임
}

4단계 - 코드 구현하기

import java.util.Scanner;

public class Q24 {
    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);
    }

    static void DFS(int number, int jarisu){
        if(jarisu == N){
            if(isPrime(number))
                System.out.println(number);
            return;
        }

        for(int i = 1; i < 10; i++){
            if(i % 2 == 0)                        // 짝수라면 탐색할 필요가 없음
                continue;
            if(isPrime(number * 10 + i))    // 소수라면 재귀 함수로 자릿수를 늘림
                DFS(number * 10 + i, jarisu + 1);
        }
    }

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

---

• Do it! 알고리즘 코딩테스트 자바 편