[백준]2023 신기한 소수 - 자바/Java

2023번: 신기한 소수

🌱풀이

알고리즘

1. 백트래킹이 핵심이다. 백트래킹의 조건은 아래와 같다.
2. DFS(a, b) 중 a는 자릿수의 숫자, b는 자리수다. DFS(2,1)은 일의 자리가 2일때다.
3. 한 자리 수에서 존재하는 소수는 2,3,5,7 뿐이다. 첫째 자리 수가 2,3,5,7일 때 자리수를 높여가며 DFS 탐색을 코드를 작성하면 된다.
4. DFS 메소드의 첫 줄에는 종료 조건을 작성한다. 목표 자리수에 도달했을 때의 숫자가 소수이면 모든 조건을 만족했으므로 출력 한다.
5. 아래 1부터 9까의 반복문은 모듈러 연산을 통해 소수를 판단한다. 소수가 아니면 넘기고, 소수로 판명되면 자릿수를 높여 DFS 메소드를 호출해 재귀 함수를 만든다.
6. 이 때 소수 판명은 메소드를 따로 작성해주는게 깔끔하다.

메모리 : 11552KB, 시간 : 820ms

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
	static int N;
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		//한 자리 수에서 소수는 2,3,5,7 뿐이다. 자리수별 소수 조건을 걸어줘서 백트래킹 하기
		N = Integer.parseInt(br.readLine());
		//한 자리에서 소수인 것부터 탐색
		DFS(2,1);
		DFS(3,1);
		DFS(5,1);
		DFS(7,1);
	}
	static void DFS(int number, int J) {
		//해당 자리수에 도달하면
		if(J == 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, J+1);
		}
	}
	static boolean isPrime(int num) {
		for(int i = 2; i<=num/2; i++) {
			if(num%i == 0) return false;
		}
		return true;
	}
}

---

🪴코드 리뷰

🌿메모리 : 11568KB, 시간 : 80ms

백트래킹 조건을 좀 더 섬세하게 설정하면 코드의 성능을 높일 수 있다. 아래 코드는 소수 판별 메소드에서 반복문의 범위를 변경했다. 기존 코드에서는 i <= num/2 였지만 여기선 i*i <= num 이다. 소수를 판별하는 알고리즘에는 여러가지가 있을 수 있는데, Conclusion의 블로그를 참고해보자.

최초 코드의 조건은 무척 단순한데, 자기 자신의 절반보다 큰 수 중에서 자기 자신을 나눌 때 0이 되는 숫자는 존재하지 않기 때문이다. 여기서 좀 더 응용하면, 해당 숫자의 제곱근까지만 확인하는 방식이다. 도저히 이해가 안되면 외우는 것도 방법이다.

💡 풀이자 : 본인

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
	static int N;
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		//한 자리 수에서 소수는 2,3,5,7 뿐이다. 자리수별 소수 조건을 걸어줘서 백트래킹 하기
		N = Integer.parseInt(br.readLine());
		//한 자리에서 소수인 것부터 탐색
		DFS(2,1);
		DFS(3,1);
		DFS(5,1);
		DFS(7,1);
	}
	static void DFS(int number, int J) {
		//해당 자리수에 도달하면
		if(J == 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, J+1);
		}
	}
	static boolean isPrime(int num) {
		for(int i = 2; i*i<=num; i++) {
			if(num%i == 0) return false;
		}
		return true;
	}
}

---

🌿메모리 : 11500KB, 시간 : 88ms

백트래킹 조건을 좀 더 자세하게 넣어봤는데 시간이 증가했다. 백준 서버 이슈일수도 있는데 성능 차이는 크게 안나는 것 같다. 제곱근까지만 검사하는걸로 엥간하면 커버가 되는 것 같다.

💡 풀이자 : 본인

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
	static int N;
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		//한 자리 수에서 소수는 2,3,5,7 뿐이다. 자리수별 소수 조건을 걸어줘서 백트래킹 하기
		N = Integer.parseInt(br.readLine());
		//한 자리에서 소수인 것부터 탐색
		DFS(2,1);
		DFS(3,1);
		DFS(5,1);
		DFS(7,1);
	}
	static void DFS(int number, int J) {
		//해당 자리수에 도달하면
		if(J == N) {
			if(isPrime(number)) System.out.println(number);
			return;
		}
		for(int i = 1; i<10; i++) {
			if( i % 2 == 0) continue; //소수가 아님
			if( J > 1 && number % 5 == 0) continue;
			if( J > 1 && sumOfJarisu(number) % 3 == 0) continue;
			if(isPrime(number*10+i)) DFS(number * 10 +i, J+1);
		}
	}
	static boolean isPrime(int num) {
		for(int i = 2; i*i<=num; i++) {
			if(num%i == 0) return false;
		}
		return true;
	}
	static int sumOfJarisu(int num) {
		String stringNumber = String.valueOf(num);
		int sum = 0;
		for(int i = 0; i<stringNumber.length(); i++) {
			sum += stringNumber.charAt(i) -'0';
		}
		return sum;
	}
}

---

Conclusion

• 소수 판별 알고리즘 익혀두기
• 첫째 자리수를 기준으로 자릿수를 높여가며 판단하는게 깊이 우선 탐색과 닮아있지 않은가? 이건 감각의 영역인 것 같다. 이런 발상이 안되면 문제를 많이 풀어서 감각을 만들어주는 수 밖에는 없다.
• 난 문제를 많이 풀어봐야한다.

소수(Prime Number) 구하기 효율적 알고리즘 :: 코드자몽