[프로그래머스 연습문제 level_2 ] 소수찾기

 

import java.util.*;

class Solution {
    static HashSet<Integer> numberSet = new HashSet<>(); // Set 중복제거
    
    public int solution(String numbers) {
        int answer = 0;
        dfs("", numbers);
        
        Iterator<Integer> itr = numberSet.iterator();
        while(itr.hasNext()){
            int number = itr.next();
            if(isSosu(number))
                answer++;
        }
        
        return answer;
    }
    
    static void dfs(String comb, String others){
        // 현재 조합을 set에 추가한다
        if(!comb.equals(""))
            numberSet.add(Integer.valueOf(comb));
        for(int i=0; i<others.length(); i++){
            dfs(comb+others.charAt(i), others.substring(0,i)+others.substring(i+1));
        }
    }
    
    static boolean isSosu(int number){
        // 1. 0과 1은 소수가 아니다
        if(number == 0 || number == 1) return false;
        
        // 2. 에라토스테네스의 체의 limit을 계산한다
        int limit = (int)Math.sqrt(number);
        
        // 3. 에라토스테네스의 체에 따라 limit까지만 배수 여부를 확인한다
        for(int i=2; i<= limit; i++){
            if(number % i == 0) return false;
        }
        return true;
    }
}

 

 

문제를 푸는 관건은 dfs 등의 방식으로 모든 조합의 수를 구하는 것과, 소수를 판별하는 로직을 아는 것이다.

 

어떻게 풀어야 할지는 아는데 구현하는게 쉽지 않아서 영상에서 도움을 받았다.

 

출처 : https://www.youtube.com/watch?v=pF368QqdQb4