문제 설명
한자리 숫자가 적힌 종이 조각이 흩어져있습니다. 흩어진 종이 조각을 붙여 소수를 몇 개 만들 수 있는지 알아내려 합니다.
각 종이 조각에 적힌 숫자가 적힌 문자열 numbers가 주어졌을 때, 종이 조각으로 만들 수 있는 소수가 몇 개인지 return 하도록 solution 함수를 완성해주세요.
제한사항
- numbers는 길이 1 이상 7 이하인 문자열입니다.
- numbers는 0~9까지 숫자만으로 이루어져 있습니다.
- "013"은 0, 1, 3 숫자가 적힌 종이 조각이 흩어져있다는 의미입니다.
입출력 예
| numbers | return |
|---|---|
| "17" | 3 |
| "011" | 2 |
예제 #1
[1, 7]으로는 소수 [7, 17, 71]를 만들 수 있습니다.
예제 #2
[0, 1, 1]으로는 소수 [11, 101]를 만들 수 있습니다.
- 11과 011은 같은 숫자로 취급합니다.
나의 풀이
DFS를 사용하였다.
import java.util.*;
class Solution {
// 노드 체크여부
static boolean[] checked;
// numbers를 split으로 자른 배열
static String[] numArr;
// DFS 깊이
static int depth = 0;
// 조합된 값
static String currentVal = "";
// 중복 값 제거
static HashSet<Integer> hs = new HashSet<>();
public int solution(String numbers) {
numArr = numbers.split("");
checked = new boolean[numArr.length];
DFS(depth, currentVal);
// answer = hs 요소 모두 소수 판별해서 뽑아낸 값의 개수
int answer = (int)hs.stream().filter(x ->isPrime(x)).count();
return answer;
}
// 소수 판별
static boolean isPrime(int num){
if(num<2) { return false; }
for(int i=2; i<=Math.sqrt(num); i++){
if(num%i==0) { return false; }
}
return true;
}
// DFS
static void DFS(int depth, String currentVal){
// 1. 모두 탐색완료 시
if(depth > numArr.length) return;
for(int i=0; i<numArr.length; i++){
// 2. 탐색하지않은 노드는
if(!checked[i]){
// 탐색전 해당 노드는 탐색했다고 표시해줌
checked[i] = true;
// 현재조합된 값 + numbers 자른 요소 끼리 또 조합하고 set에 삽입
hs.add(Integer.valueOf(currentVal+numArr[i]));
// 3. 더한값 갖고 인접한 다른 노드 방문 (재귀적 탐색)
DFS(depth+1, currentVal+numArr[i]);
// 탐색했으면 다시 표시 초기화
checked[i]= false;
} // "17"이 들어오면 [1, 17, 7, 71] 순으로 set에 삽입됨
}
}
}