2023번 - 신기한 소수(bfs, 백트래킹)

문제:

7331은 소수인데, 733도 소수 73도 소수 7도 소수이다.

이런 숫자를 신기한 소수라고 하자.

숫자 N이 주어졌을 때, N자리 수 모든 신기한 소수들을 출력해라. 

 

 

풀이:

예시 7331에서 고려해야 할 숫자는 7 73 733 7331 모두 4개이다.

만약 왼쪽부터 첫 자리 수가 소수가 아니라면 그 이후 수는 고려할 필요가 없다.

즉, 왼쪽자리 숫자부터 고려하면 된다는 뜻이다.

신기한 소수를 만들려면 아래와 같은 규칙이 동반되어야 할 것이다.

• 왼쪽부터 첫째 자리 수가 소수이려면, {2, 3, 5, 7} 중 하나여야 한다.
• 둘째 자리 이상의 수가 소수이려면, {1, 3, 7, 9} 중 하나가 마지막수로 붙어야 한다.
  어떤 수든 두자리 수 이상의 수가 소수이려면 {0, 2, 4, 5, 6, 8}은 마지막 숫자로 붙으면 안된다.

첫번째 규칙은 한자리 수 소수를 생각해보면 이해될 것이고,
두번째 규칙은 아무 숫자나 두자리 수 이상의 수를 생각해보면 이해될 것이다.

 

위 규칙을 고려해 메서드를 작성하면 아래와 같다.

static void backTracking(int N, int num) {
    if ((int) Math.log10(num) + 1 == N) {
        System.out.println(num);
        return;
    }

    for (int i = 0; i < 4; i++) {
        int newNum = num * 10 + next[i];
        if (isPrime(newNum)) {
            backTracking(N, newNum);
        }

    }
}

num은 2, 3, 7, 9가 될 수 있으므로 위 메서드는 4번 실행된다.

next에는 {1, 3, 7, 9}가 저장되어 있으며, 만일 새로 만든 수가 소수라면, 다시 재귀함수에 넣어준다.

만일 자릿수가 N이 되면 해당 수를 출력한다.

 

전체코드:

import java.util.*;

public class Main {
    static int[] next = new int[]{1, 3, 7, 9};

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();

        // 2, 3, 5, 7로 시작해야 함
        // 이후 0, 2, 4, 5, 6, 8은 나올 수 없음
        // 그렇다면 짝수로 나눠볼 필요가 없어짐

        // 2. backTracking 풀이
        int[] first = new int[]{2, 3, 5, 7};
        for (int num : first) {
            backTracking(N, num);
        }
    }

    static boolean isPrime(int n) {
        for (int i = 3; i <= n/3; i+=2) { // 짝수는 고려 안해도 됨
            if (n % i == 0) {
                return false;
            }
        }
        return true;
    }

    static void backTracking(int N, int num) {
        if ((int) Math.log10(num) + 1 == N) {
            System.out.println(num);
            return;
        }

        for (int i = 0; i < 4; i++) {
            int newNum = num * 10 + next[i];
            if (isPrime(newNum)) {
                backTracking(N, newNum);
            }

        }
    }
}

backTracking 과정에서 next 배열이 반복생성되지 않기 위해 static 타입으로 지정해줬다.

위에서 설명한 바와 같이 num은 2, 3, 7, 9가 될 수 있으므로 위 메서드는 4번 실행된다.

 

시행착오:

처음에는 bfs 방식으로 접근했다.

정답이였고, 성능상 문제도 없으나, 굳이 queue를 하나 더 생성해서 메모리가 낭비되는 것은 좋다고 생각하지 않는다.

분명 backTracking으로 접근할 만 했으나, 보다 익숙한 방법인 bfs 습관처럼 이용해버렸다.

아래는 bfs를 이용한 풀이이다.

import java.util.*;

public class Main {
    static int[] next = new int[]{1, 3, 7, 9};

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();

        // 2, 3, 5, 7로 시작해야 함
        // 이후 0, 2, 4, 5, 6, 8은 나올 수 없음
        // 그렇다면 짝수로 나눠볼 필요가 없어짐

        // 1. bfs 풀이
        bfs(N);
    }

    static boolean isPrime(int n) {
        for (int i = 3; i <= n/3; i+=2) { // 짝수는 고려 안해도 됨
            if (n % i == 0) {
                return false;
            }
        }
        return true;
    }

    static void bfs(int N) {
        Queue<Integer> queue = new LinkedList<>();
        queue.add(2);
        queue.add(3);
        queue.add(5);
        queue.add(7);

        while(!queue.isEmpty()) {
            int num = queue.poll();
            if ((int)Math.log10(num) + 1 == N) { // 자리수에 도달
                System.out.println(num);
                while (!queue.isEmpty()) {
                    System.out.println(queue.poll());
                }
                break;
            }

            for (int i = 0; i < 4; i++) {
                int prime = num * 10 + next[i];
                if (isPrime(prime)) {
                    queue.add(prime);
                }
            }
        }
    }
}

접근 방법이 여러개인 문제였기에 그렇게 어렵지 않은 문제였다.