프로그래머스 소수찾기(실패분석, java)

접근

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

처음에 에라토스테네스체로 접근하려고 했었다.
범위를 String으로 받는 s를 char 배열로 만든 후에 정렬하여
s로 만들 수 있는 가장 큰수를 만들었다.
이후 가장 큰수를 끝 범위로 하여 2부터 가장 큰수 사이에 존재하는 소수를 모두 표시하고
그 소수 중에 s로 만들 수 있는 수가 있는가를 표시하려고 했으나

너무 코드가 길어지기 때문에
DFS를 통해서 s를 통해 만들 수 있는 모든 숫자를 조합해서 만들고
그 숫자가 소수인지 판별하는 방법으로 접근하였다.

결국에는 크게
1. DFS를 통해서 모든 숫자 조합을 만든다.
2. 모든 숫자 조합을 만든다는 것은 각 배열의 값을 선택한다 안한다로 나눠지기 때문에 결국에는 백트래킹을 이용한 DFS를 구현한다.
3. 만들어진 수가 소수인지 판별하는 과정에서 이미 검사한 소수인지 확인하기 위해서 Map에 존재하는 Key인가를 확인하는 과정이 추가로 필요하다.
4. 그리고 소수인지 판별하는 메서드가 하나 필요하다.

풀이

import java.util.*;

class Solution {
    
    static boolean[] visited;
    static String[] str_arr;
    static int cnt;
    // 이미 검사한 소수인지 판별하기 위한 Map
    static Map<Integer,Integer> map = new HashMap<>();
    
    public int solution(String numbers) {
   
  
        
        str_arr = numbers.split("");
        visited = new boolean[str_arr.length];
        
        dfs(0,str_arr,"");
        
        return cnt;
        
        
    }
    
    //모든 숫자 조합을 만들기 위한 DFS
    static void dfs(int depth , String[] str_arr,String result){
        if(depth==str_arr.length+1){
            
             //numberformatexception: for input string: ""
            //result가 "" 빈문자열인 경우
            //Integer.parseInt에서 예외가 발생
            if(result.equals("")) return;
            
          
            int check = Integer.parseInt(result);
            
            // 소수이며 검사한 소수가 아닌 경우
            if(isPrime(check) && !map.containsKey(check)){
                cnt++;
                map.put(check,1);
            }
            return;
        }else{
            //for문을 통해서 17,71의 접근이 가능
            for(int i=0;i<str_arr.length;i++){
                // 방문한 수가 아니라면
                if(visited[i]==false){
                 visited[i]=true;
                 dfs(depth+1,str_arr,result+str_arr[i]);
                 visited[i]=false;
                 dfs(depth+1,str_arr,result);
                }
    
            }            
        }
                
    }
    //소수인지 판별하는 메서드
    static boolean isPrime(int input){
        
        if(input==0 || input==1) return false;
    
        for(int i=2;i<input;i++){
            if(input%i==0) return false;
        }     
        return true;
    }
    
}