[프로그래머스] [Level2] 소수찾기 JAVA

https://programmers.co.kr/learn/courses/30/lessons/42839

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

문제

풀이

완전탐색 + 백트래킹 문제이다
주어진 numbers 로 모든 순열을 만들어서 소수인지아닌지 판별하여 카운트를 리턴하면된다.
String -> int 형으로 바꿀 때 , "01234" 이런것도 1234 로 변환할 수 있는 메서드가 Integer 라이브러리에 있다.
Integer.valueOf 라는 메서드로 변환을 한 다음, 중복을 허용하지않는 특성의 자료구조인 Set에 저장하면 된다.

 

import java.util.*;
import java.io.*;
import java.util.stream.Collectors;
 
class Solution {
    static boolean[] check;
    static String[] split;
    static HashSet<Integer> set = new HashSet<>();
    public int solution(String numbers) {
        split = numbers.split("");
        check = new boolean[split.length];
        dfs(0,"");
        return (int)set.stream().filter(Solution::isPrime).count();
    }
    static boolean isPrime(int num){
        if(num<2) return false;
        for(int i=2;i<=(int)Math.sqrt(num);i++)
            if(num%i==0) return false;
        return true;
    }
    static void dfs(int depth,String cur){
        if(depth >split.length) return;
 
        for(int i=0;i< split.length;i++){
            if(!check[i]){
                check[i]=true;
                set.add(Integer.valueOf(cur+split[i]));
                dfs(depth+1,cur+split[i]);
                check[i]=false;
            }
        }
    }
}