SSAFY에 있으면서 했던 코테를 잠시 놓았더니 전부다 까먹어서
순열 조합 부분집합등 전부다 못푸는 지경이 되버렸다 ㅠㅠ
처음부터 다시 하려고한다!!
접근은
0. 완전 탐색을 사용 할수있는가?
//20220219
import java.util.*;
class Solution {
static private ArrayList<Integer> answer_list = new ArrayList<Integer>();
static private int[] check = new int[10];
public int solution(String numbers) {
int answer = 0;
String tmp ="";
for(int i=0;i<numbers.length();i++){
dfs("", numbers, i+1);
}
/*
for(int i : answer_list){
System.out.println(i);
}*/
for(int i=0;i<answer_list.size();i++){
if(check(answer_list.get(i))==true){
answer++;
}else{
}
}
return answer;
}
private void dfs(String now, String numbers,int size){
if(now.length()==size){
int temp_num = Integer.parseInt(now);
if(answer_list.contains(temp_num)==false){
answer_list.add(temp_num);
}
return;
}
for(int i=0;i<numbers.length();i++){
if(check[i]==0){
check[i]=1;
now+=numbers.charAt(i);
dfs(now, numbers, size);
check[i]=0;
now= now.substring(0, now.length()-1);
}
}
}
private boolean check(int num){
if(num==0) return false;
if(num==1) return false;
for(int i=2;i<num;i++){
if(num % i ==0){
return false;
}
}
return true;
}
}
import java.util.*;
class Solution {
static private boolean[] check = new boolean[10];
static Set<Integer> answer_set = new HashSet<Integer>();
public int solution(String numbers) {
int answer = 0;
String temp = "";
for(int i=0;i<numbers.length();i++){
dfs(temp, numbers, i+1);
}
Iterator<Integer> itr = answer_set.iterator();
while(itr.hasNext()){
int check = itr.next();
if(isprime(check)==true){
answer++;
}
}
return answer;
}
private void dfs(String temp, String numbers, int size){
if(temp.length()==size){
int temp_number = Integer.parseInt(temp);
answer_set.add(temp_number);
return;
}
for(int i=0;i<numbers.length();i++){
if(check[i]==false){
check[i]=true;
temp += numbers.charAt(i);
dfs(temp, numbers, size);
check[i]=false;
temp=temp.substring(0, temp.length()-1);
}
}
}
private boolean isprime(int num){
if(num==0) return false;
if(num==1) return false;
for(int i=2;i<num;i++){
if(num%i==0){
return false;
}
}
return true;
}
}