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

programmers.co.kr/learn/courses/30/lessons/42587programmers.co.kr/learn/courses/30/lessons/42839

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

문제풀이

numbers의 길이가 7이하 이기때문에 완전 탐색하는데 아무 문제가 없다.

자리가 바뀔 수 있기때문에 순열을 사용하였다. 거기에 numbers의 자리 갯수마다 틀려질 수 있기 때문에

for문을 이용하여 구해야 되는 자릿수를 증가 시켜주면서 순열을 돌렸다.

• Set을 사용하였는데 사용한 이유는 011 같은 경우 11이 중복되는 경우가 있다 그래서 set.contains을
  사용하여 존재 하면 이미 검사를 했기 때문에 소수를 찾을 필요가 없기에 return 해주었다. 

코드

import java.util.HashSet;
import java.util.Set;

class Solution {
    static int answer;
    static String number;
    static Set<Integer> set;
    
    public int solution(String numbers) {
        number = numbers;
        set = new HashSet<>();
        
        for(int i =1; i<=numbers.length(); i++) {
        	permutaion(0,numbers,new char[number.length()], new boolean[number.length()], i);
        }
        
        return answer;
    }
    
    public void permutaion(int cnt, String check, char[] result, boolean[] isChecked, int end){
        if(cnt == end){
        	String temp ="";
        	int index =0;
        	for(int i=0; i<check.length(); i++) {
                if(isChecked[i]==true)temp += result[index++];
			}
        	
        	int num = Integer.parseInt(temp);
        	if(set.contains(num)) return;
        	
            if(findPrime(num)) {
            	set.add(num);
            	answer++;
            }
            return;
        }
        
        for(int i=0; i<check.length(); i++){
            if(isChecked[i]==true) continue;
            
            result[cnt] = check.charAt(i);
            isChecked[i] = true;
            permutaion(cnt+1, check, result, isChecked, end);
            isChecked[i] = false;
        }
    }
    
    public boolean findPrime(int num){
    			if(num < 2) return false;
    			
    			if(num == 2) return true;
    	        
    			for(int i = 2; i < num; i++) {
    				if(num % i == 0) {
    					return false;
    				}
    			}
    			return true;
    }
}