[프로그래머스/JAVA] - 소수 찾기(완전탐색)

 

코딩테스트 연습 - 소수 찾기 | 프로그래머스 스쿨 (programmers.co.kr)

프로그래머스

 

문제설명

 

한자리 숫자가 적힌 종이 조각이 흩어져있습니다. 흩어진 종이 조각을 붙여 소수를 몇 개 만들 수 있는지 알아내려 합니다.

각 종이 조각에 적힌 숫자가 적힌 문자열 numbers가 주어졌을 때, 종이 조각으로 만들 수 있는 소수가 몇 개인지 return 하도록 solution 함수를 완성해주세요.

 

풀이

import java.util.*;
class Solution {
    public int solution(String numbers) {
        int answer = 0;
         
        HashSet<Integer> set =new HashSet<>();
        
        allnumbers("",numbers,set);
        
        while(set.iterator().hasNext()){
            int n = set.iterator().next();
            set.remove(n);
            if(is_prime(n)){
                answer++;
            }
  
        }
        return answer;
    }
    
    //소수찾기
    public boolean is_prime(int n){
        if(n == 0 || n ==1) return false;
        for(int i=2; i*i<=n;i++){
            if(n%i==0) return false; 
        }  
        return true;
    }
    
    //숫자 모두 찾기
    public void allnumbers(String pre,String str, HashSet<Integer> set){
        int n = str.length();
 
        if(!pre.equals("")){
            set.add(Integer.valueOf(pre));
        }
        
        for(int i=0; i<n; i++){
            allnumbers(pre+str.charAt(i), str.substring(0,i)+str.substring(i+1,n),set);
        }
    }
}

 

set.iterator() : set의 요소를 반복하기 위한 반복자

iterator.hasNext() : 반복자를 통해 다음 요소가 있는지 확인하는 메서드(T/F 반환)

set.iterator().next() : next()를 통해 다음요소를 반환하고 반복자의 위치를 한 칸 이동