[백준] 2023 - 신기한 소수 (java)

[백준] 2023 - 신기한 소수 링크

문제 요약

• 1~8의 숫자가 주어진다.
• 주어진 숫자 N 자릿수 숫자들에서 소수를 구한다. (ex: N=4 => 1000~9999)에서 소수는?
• 다만 맨 앞에서부터 1~N 자리의 숫자는 모두 소수여야 한다.

7331은 소수인데, 신기하게도 733도 소수이고, 73도 소수이고, 7도 소수

풀이과정

백트래킹

N자리 숫자가 될때까지 숫자를 붙여나간다.

예를 들어 1234라는 숫자를 만들어야 한다면 1 => 12 => 123 => 1234

이 N자리 숫자를 만드는 과정 속에서 소수인지 판별한다.

순회가 너무 많을 것 같음

1자리에서 N자리를 만들어가며 한자리마다 1~9의 숫자를 모두 활용해 소수인지 체크한다면 시간복잡도 효율이 매우 떨어질 것이다.

메모이제이션 없이 주어지는 숫자를 가지고 소수인지 바로 판별할 것이기 때문에 자릿수가 많다면 반복이 많아질 것이다.

아래와 같은 소수의 특성이 있어서 활용해 이를 최적화 할 수 있을 것 같았다.

소수 특(1)

1자리 소수의 경우 [2, 3, 5, 7] 이다.

즉 주어지는 N과 상관없이 맨 앞에는 위의 4개의 숫자만 올 수 있다.

소수 특(2)

2자리 이상의 소수일 경우 반드시 [1, 3, 7, 9]로만 끝날 수 있다.

3795 => 5로 반드시 나뉜다.
379[짝수] => 2로 반드시 나뉜다.

끝난다 라는 것은 마지막 자리의 숫자를 의미하는데 결국 주어지는 N에 대해 1~N 자리 숫자가 모두 소수여야한다는 요구사항이 있기 때문에 [1, 3, 7, 9]라는 숫자만 활용해도 충분할 것이다.

예를 들어 347는 소수이지만 34는 소수가 아니며 문제에서 구해야하는 조건이 아니다.

풀이 코드

import java.util.Scanner;

public class boj2023_신기한소수 {
    static int[] firstPrimeArr = {2, 3, 5, 7};
    static int[] notFirstPrimeArr = {1, 3, 7, 9};

    public static void main(String[] args) {
        int number = Integer.parseInt(new Scanner(System.in).nextLine());
        for (int i = 0; i < 4; i++) {
            per(number, new StringBuilder().append(firstPrimeArr[i]));
        }
    }

    static void per(int maxCount, StringBuilder currentStr) {
        if (maxCount == currentStr.toString().length()) {
            System.out.println(currentStr);
            return;
        }
        for (int i = 0; i < 4; i++) {
            int currentNumber = Integer.parseInt(currentStr.toString() + notFirstPrimeArr[i]);
            if (isPrime(currentNumber)) {
                per(maxCount, currentStr.append(notFirstPrimeArr[i]));
                currentStr.setLength(currentStr.length() - 1);
            }
        }
    }

    static boolean isPrime(int number) {
        if (number == 1) {
            return false;
        }
        if (number <= 3) {
            return true;
        }
        for (int i = 2; i <= Math.sqrt(number); i++) {
            if (number % i == 0) {
                return false;
            }
        }
        return true;
    }
}

초기 첫 자리의 경우 [2,3,5,7]로 Stringbuilder에 넣어주고

백트래킹으로 [1,3,7,9]를 붙여가며 소수인지 검사하며 N자리를 만들어 간다.