java 프로그래머스 [완전탐색] _소수 찾기

 

출제 링크 : programmers.co.kr/learn/courses/30/lessons/42839

코딩테스트 연습 - 소수 찾기

 

---

import java.lang.*;
import java.util.*;

class Solution {
    
    static int answer = 0;
    static boolean[] check = new boolean[7];
    static ArrayList<Integer> arr = new ArrayList<>();
    
    public int solution(String numbers) {
        
        String temp = "";
        
        for(int i=1; i <= numbers.length(); i++){
            bfs(numbers, temp, i);
        }
        
        for(int x : arr) {
            cal(x);
        }
        
        return answer;
    }
    
    public static void bfs(String numbers, String temp, int i){
        if(temp.length() == i) {
            if(!arr.contains(Integer.parseInt(temp)))
                arr.add(Integer.parseInt(temp));
                return;
        }
        
        for(int j=0; j < numbers.length(); j++) {
            if(check[j]) continue;
            
            temp += numbers.charAt(j);
            
            check[j] = true;
            bfs(numbers, temp, i);
            check[j] = false;
            
            temp = temp.substring(0, temp.length() - 1);
        }
    }
    
    public static void cal(int n) {
        if(n == 0 || n == 1) return;
        
        
        for(int i=2; i <= Math.sqrt(n); i++) {
            if(n % i == 0) return;
        }
        
        answer++;
    }
}