[알고리즘] 백준 2023 신기한 소수 -백트랙킹- 자바 코틀린

 

 

 

 

그동안 시간관계상 알고리즘 풀이를 못하였는데 약 두달만에 풀어봤네요. 오랜만의 풀이라 안그래도 없던 알고리즘 실력도 다 떨어졌는데 주요 알고리즘과 스탠다드한 문제 풀이로 감도 되찾고 실력을 쌓으려고합니다.. ㅎㅎ 시간 여유도 생겼으니 열심히 해야겠습니다. 

 

youngest-programming.tistory.com/382

[알고리즘] 스터디 계획표

예전 공부 계획표 참고하면서 분류당 한문제씩 풀어볼까 생각중입니다.

 

 

---

www.acmicpc.net/problem/2023

2023번: 신기한 소수

오늘은 백준 2023 신기한 소수 문제를 풀어봤습니다.

N자리수의 자연수들 중 1의자리부터 N자리까지 모두 소수인 자연수를 판별하는 문제로

소수랑 백트랙킹이 엮인 스탠다드한 문제였습니다.

 

처음 다음과 같이 에라토스테네스의 체로 최대 자리수의 소수판별 배열을 만들어서 풀이했는데 메모리 초과로 통과하지못하였습니다.

import java.util.Scanner;

class Main {
    private static int N;
    private static boolean[] prime;
    private static StringBuilder sb = new StringBuilder();

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        int max = (int) Math.pow(10f, N); // N=2 -> 100
        prime = new boolean[max];
        makePrime(max);
        dfs("", 0);
        System.out.println(sb.toString());
    }

    private static void dfs(String num, int depth) {
        if (depth == N) {
                sb.append(num).append("\n");
            return;
        }
        for (int i = 1; i <= 9; i++) {
            int currentNum = Integer.parseInt(num + i);
            if (!prime[currentNum]) {
                dfs(currentNum + "", depth + 1);
            }
        }

    }

    private static void makePrime(int n) {
        prime[0] = true;
        prime[1] = true;
        for (int i = 2; i <= Math.sqrt(n); i++) {
            if (prime[i]) continue;
            for (int j = i * i; j < prime.length; j += i) {
                prime[j] = true;
            }
        }
    }


}

 

 

그래서 소수판별방식을 그떄그떄 수를 매개변수로 받아서 판별하게 변경으로써 통과할 수 있었습니다.

풀이는 다음과 같습니다.

[Java]

import java.util.Scanner;

class Main {
    private static int N;
    private static StringBuilder sb = new StringBuilder();

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        dfs("", 0);
        System.out.println(sb.toString());
    }

    private static void dfs(String num, int depth) {
        if (depth == N) {
            sb.append(num).append("\n");
            return;
        }
        for (int i = 1; i <= 9; i++) {
            int currentNum = Integer.parseInt(num + i);
            if (isPrime(currentNum)) {
                dfs(currentNum + "", depth + 1);
            }
        }

    }

    private static boolean isPrime(int n) {
        // 0, 1
        if (n < 2) return false;
        // 2
        if (n == 2) return true;

        for (int i = 2; i < n; i++) {
            // 소수 X
            if (n % i == 0) return false;
        }
        return true;
    }


}

 

[Kotlin]

import java.util.*


private var N = 0
private val sb = StringBuilder()
fun main(args: Array<String>) {
    val sc = Scanner(System.`in`)
    N = sc.nextInt()
    dfs("", 0)
    println(sb.toString())
}

private fun dfs(num: String, depth: Int) {
    if (depth == N) {
        sb.append(num).append("\n")
        return
    }
    for (i in 1..9) {
        val currentNum = (num + i).toInt()
        if (isPrime(currentNum)) {
            dfs(currentNum.toString() + "", depth + 1)
        }
    }
}

private fun isPrime(n: Int): Boolean { 
    if (n < 2) return false // 0, 1
    // 2
    if (n == 2) return true
    for (i in 2 until n) { // 소수 X
        if (n % i == 0) return false
    }
    return true
}

 

 

뎃글과 공감은 큰 힘이 됩니다. 감사합니다.!!