[알고리즘] 프로그래머스-소수찾기 (완전탐색)

1. 문제

2. 코드

순열을 이용해서 모든 경우의 수를 완전탐색하는 문제였다. dfs알고리즘을 순열에 적용했다고 생각하면된다. 현재 입력받은 문자열을 배열에 int로 저장을하고, permutation 메소드를 재귀로 돌려주었다. 방문한 곳은 true로 표시를하고 다시 방문을 하지 않았다. base case에서는 전부다 선택을 안한 케이스와, 소수는 2이상부터 있으므로 0과 1은 넣어주지 않았다. 또한 맨앞이 0으로 시작하는 케이스도 세지 않았다. 그리고 중복되는 경우의 수들이 있어서 map을 이용해서 중복된 값을 제거해주었다.

 

마지막으로 map에 넣은 키값들을 다시 빼내서 정수로 바꾸고 소수판별 메소드로 검사를해주었다. 

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

class Solution {
    
    public static Map<String, String> map;
    
    public void permutation(int numberArr[], boolean visited[], String answer, int depth, int n){

        //base case 정의
        if(n == depth){
            
            if(!"".equals(answer) && !"0".equals(answer) && !"1".equals(answer)){
                if(answer.charAt(0) == '0'){
                    return;
                }                
                map.put(answer, answer);
            }
            
            return;
        }
        
        for(int i=0;i<numberArr.length;i++){
            
            //방문한곳은 안넣어줌
            if(visited[i] == true){
                continue;
            }
            
            visited[i] = true;
            permutation(numberArr, visited, answer + String.valueOf(numberArr[i]), depth+1, n);
            visited[i] = false;
            permutation(numberArr, visited, answer, depth+1, n);
        }   
    }
    
    public boolean isPrime(Integer num){
        boolean flag = true;
        
        for(int i=2;i<num;i++){
            if(num%i == 0){
                flag = false;
                return flag;
            }
        }
        
        return flag;
    }
    
    public int solution(String numbers) {
        int answer = 0;
        map = new HashMap<>();
        
        int len = numbers.length();
        int numberArr[] = new int[len];      
        boolean visited[]= new boolean[len];      
        
        for(int i=0;i<numbers.length();i++){
             numberArr[i] = Integer.parseInt(numbers.charAt(i)+"");
        }
        
        permutation(numberArr, visited, "", 0, len);

        //소수검사
        for ( String key : map.keySet() ) {
            Integer num = Integer.parseInt(key);
            
            if(isPrime(num) == true)
                answer++;
        }
        
        return answer;
    }
}