[java] 문제 024 (백준 2023)

문제

신기한 소수

 

교재 풀이

import java.util.*;
public class P2023_신기한소수 {
  static int N;
  public static void main(String[] args) {
    Scanner in = new Scanner(System.in);
    N = in.nextInt();
// 일의 자리 소수는 2 3 5 7 이므로 4개 수에서만 시작
    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;
  }
}

내 풀이) 24.6.12에 풀고 틀린 코드

import java.util.*;
import java.io.*;

public class Main
{
    static ArrayList<Integer> ans;
    static int n;

	public static void main(String[] args) throws IOException{
        Scanner sc=new Scanner(System.in);
        n=sc.nextInt();
        ans=new ArrayList<Integer>();

        dfs(2, 1);
        dfs(3, 1);
        dfs(5, 1);
        dfs(7, 1);

        Collections.sort(ans);

        for(int i:ans){
            System.out.println(i);
        }

	}

	public static void dfs(int num, int jarisu){
        if(jarisu<n){
            for(int i=1;i<=10;i++){
                if(isPrime(num*10+i)){
                    dfs(num*10+i, ++jarisu);
                }
            }
        }

        if (jarisu==n && isPrime(num)){
            ans.add(num);
        }
        }

    public static boolean isPrime(int num){
	    if(num==1) return false;
	    if(num==2) return true;
	    if(num%2==0) return false;

	    for(int i=3;i<Math.sqrt(num);i+=2){
	        if(num%i==0){
	            return false;
	        }
	    }

	    return true;
	    }

}

내 풀이) 24.6.12에 틀린 코드, 고쳐서 맞힌 코드

import java.util.*;
import java.io.*;

public class Main {
    static ArrayList<Integer> ans;
    static int n;

    public static void main(String[] args) throws IOException {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        ans = new ArrayList<Integer>();

        dfs(2, 1);
        dfs(3, 1);
        dfs(5, 1);
        dfs(7, 1);

        Collections.sort(ans);

        for (int i : ans) {
            System.out.println(i);
        }
    }

    public static void dfs(int num, int jarisu) {
        if (jarisu < n) {
            for (int i = 1; i <= 9; i++) {// 1부터 9까지 확인if (isPrime(num * 10 + i)) {
                    dfs(num * 10 + i, jarisu + 1);// 다음 자리로 넘어감
                }
            }
        } else {
            if (isPrime(num)) {
                ans.add(num);
            }
        }
    }

    public static boolean isPrime(int num) {
        if (num == 1) return false;
        if (num == 2) return true;
        if (num % 2 == 0) return false;

        for (int i = 3; i <= Math.sqrt(num); i += 2) {// i <= Math.sqrt(num) 수정if (num % i == 0) {
                return false;
            }
        }

        return true;
    }
}

설명

• 6.12 내 코드 수정본 설명 -> 챗 지피티 선생님이 바로 잡아줌
  • dfs 메서드의 재귀 호출에서 jarisu의 값을 올바르게 관리하도록 수정했습니다. jarisu++ 대신 jarisu + 1을 사용하여 다음 자리로 넘어갈 때마다 정확한 값을 전달하도록 했습니다.
  • isPrime 메서드의 조건을 올바르게 수정했습니다. 소수 판별을 위해 i <= Math.sqrt(num)을 사용하여 정확하게 검사하도록 했습니다.
  • 자리수 검사를 위한 범위를 1부터 9까지로 설정하여 유효한 자릿수만 확인하도록 했습니다.

 

• ++jarisu가 문제가 되는 이유는 jarisu의 값을 증가시킨 후, 그 값을 다음 재귀 호출에 사용하기 때문입니다. 즉, 재귀 호출 이후에도 증가된 값이 유지되어, 원하는 대로 자릿수를 관리할 수 없습니다.코드에서 ++jarisu를 사용하면, jarisu의 값이 증가된 상태로 재귀 호출이 이루어지게 되며, 이후에도 증가된 값이 유지됩니다. 이는 jarisu의 값을 정확하게 관리하는 데 문제가 됩니다

public static void dfs(int num, int jarisu) {
    if (jarisu < n) {
        for (int i = 1; i <= 9; i++) {
            if (isPrime(num * 10 + i)) {
                dfs(num * 10 + i, ++jarisu);  // jarisu 값을 증가시키고, 증가된 값을 사용
            }
        }
    } else {
        if (isPrime(num)) {
            ans.add(num);
        }
    }
}

 

• 위 코드에서는 ++jarisu를 사용하기 때문에, 재귀 호출 시 jarisu의 값이 증가된 상태로 유지됩니다. 이는 여러 번의 재귀 호출 동안 jarisu의 값을 정확히 추적하지 못하게 합니다.재귀 호출 시 jarisu의 값을 증가시키고, 증가된 값을 사용하는 대신, 원래의 값을 유지하면서 다음 자릿수를 처리해야 합니다. 이를 위해 jarisu + 1을 사용합니다.설명결론
  • jarisu + 1을 사용하면, 현재 jarisu 값을 변경하지 않고, 재귀 호출 시 증가된 값을 전달할 수 있습니다. 이는 재귀 호출 이후에도 원래의 jarisu 값을 유지하게 하여, 정확한 자릿수 관리를 가능하게 합니다.
• ++jarisu를 사용하는 대신 jarisu + 1을 사용하면, 재귀 호출 시 jarisu 값을 정확하게 관리할 수 있습니다. 이는 재귀 호출이 중첩되는 상황에서 특히 중요합니다. 따라서 올바른 자릿수 관리를 위해 jarisu + 1을 사용해야 합니다.

 

 

NullPointerException이 발생하는 이유는 ans 리스트가 초기화되기 전에 dfs 메서드에서 접근하려고 하기 때문입니다. dfs 메서드에서 ans 리스트를 사용하기 전에 초기화가 되어 있어야 합니다. 그러나 현재 코드에서는 dfs 메서드가 ans 리스트가 초기화되기 전에 호출되고 있습니다.

=> NullPointerException이 뜨면 이런 종류의 이유 때문이구나 추측할 수 있게 됨