프로그래머스_소수 찾기

// 알고리즘

1. 순열 + 조합문제

 

2. 주어진 문자열을 각가 나눔

 -> char 배열을 사용하여 각각 나눔

 

3. 1개 뽑는 경우 부터 다 뽑는 경우까지 조합을 만듦

 

4. 만들어 조합을 HashSet에 저장

 -> ex) 011과 11이 같은 수 이므로 set을 사용하여 중복데이터를 없애줌.

 

5. 만들어진 set을 가지고 소수를 판별하면 됨

 -> 2부터 시작하여 소수인지 판별

import java.util.*;

class Solution {
    static int ans;
    static char[] num;
    static boolean[] v;
    static HashSet<Integer> set;
    
    public int solution(String numbers) {
        
        
        num = numbers.toCharArray();
        v = new boolean[num.length];
        set = new HashSet<Integer>();
        
        for(int i = 1 ; i <= v.length; i++){
            combination(0,i, new int[i+1]);    
        }
        
        check();
        return ans;
    }
    
    static public void check(){
        
       L:for(Integer result : set){
           if(result < 2) continue L;
            for(int i = 2; i*i <= result ; i++){
                if(result % i == 0) continue L;
            }    
           ans++;
        }
        
        
    }
    
    static public void combination(int idx,int size,int[] list){
        
        if(idx == size){
            String str = "";
            
            for(int i= 0; i < size; i++){
                str += list[i];
            }
            
            if(str.length() == 0) return;
            int result = Integer.parseInt(str);
            set.add(result);
            return;
        }
    
        
        for(int i = 0; i<v.length; i++){
            if(v[i]) continue;
            v[i] = true;
            list[idx] = num[i]-'0';
            combination(idx+1,size,list);
            v[i] = false;
        }
        
    }
}

 

※ 이클립스를 안쓰고 풀려니까 어려움을 많이 느낌. 앞으로 자동완성을 사용하지 않고 직접 구현하는 연습이 필요할거같음.