n개의 값 중 n개를 뽑는 순열을 백트래킹으로 찾다 보면 모든 경우의 수가 나온다.
checkedNumbers
사용numbers.length
개의 값 중에서 numbers.length
개의 숫자를 뽑는 순열을 찾는 것처럼 Backtracking 한다.checkedNumbers
에 있는 경우를 제외한 Backtracking 의 모든 과정에서 currNumber
가 소수인지 판별하여 소수가 맞으면 answer
을 1 증가 시킨다.answer
을 반환한다.import java.util.ArrayList;
import java.util.List;
class Solution {
static String numbers;
static boolean[] visited;
static List<Integer> checkedNumbers = new ArrayList<>();
static int answer = 0;
public int solution(String numbers) {
this.numbers = numbers;
visited = new boolean[numbers.length()];
findPrimeNumber(0);
return answer;
}
public void findPrimeNumber(int currNumber) {
if (checkedNumbers.contains(currNumber)) {
return;
}
checkedNumbers.add(currNumber);
if (isPrimeNumber(currNumber)) {
answer++;
}
for (int i = 0; i < numbers.length(); i++) {
if (visited[i]) {
continue;
}
visited[i] = true;
int nexNumber = Integer.parseInt(String.valueOf(currNumber) + numbers.charAt(i));
findPrimeNumber(nexNumber);
visited[i] = false;
}
}
public boolean isPrimeNumber(int number) {
if (number < 2) {
return false;
}
for (int i = 2; i <= Math.sqrt(number); i++) {
if (number % i == 0) {
return false;
}
}
return true;
}
}