[고득점kit/완전탐색] 소수찾기

사실 처음엔 n 자리에 올 수 있는 수 / 올 수 없는 수 이렇게 나눠서 풀려다가 이게 효율이 더 떨어질 것 같다는 생각이 팍!들어서 그냥 구할 수 있는 모든 숫자의 조합을 구하고 소수 판별을 하기로 결정했다!

---

import java.util.*;
class Solution {
    HashSet<Integer> numberSet = new HashSet<>();
    public void recursive(String comb, String others){
        //comb: 여태까지 조합된 숫자
        //others: 사용하지 않은 숫자
        //1. 현재 조합된 숫자를 set에 추가해줌
        if(!comb.equals(""))    //comb가 빈스트링이 아닐때
            numberSet.add(Integer.valueOf(comb)); 
        //2. 남은 숫자 중 한 개를 더해 새로운 조합을 만듦 
        for(int i = 0; i < others.length(); i++){
            recursive(comb + others.charAt(i), others.substring(0, i) + others.substring(i+1)); //(others에서 아직 쓰지 않은 숫자 중 하나만 쓰길 원함, 사용한 i는 빼기 위해 0~i-1까지, i+1~끝까지만 남김)
        }
         
    }
    public boolean isPrime(int num){
        if(num == 0 || num ==1) return false;
        
        int lim = (int)Math.sqrt(num);
        
        for(int i = 2; i <= lim; i++){
            if(num % i == 0) return false;
        }
        return true;
    }
    public int solution(String numbers) {
        int count = 0;
        //모든 조합의 숫자를 만듦
        recursive("", numbers); //(아직 조합된 숫자가 없음, 처음 주어진 숫자)
        //소수의 개수만 세기
        Iterator<Integer> it = numberSet.iterator();    //numberSet이 실체. numberSet안에 요소를 다 사용할 때
        while(it.hasNext()){
            int number = it.next();
            if(isPrime(number)) count++;
        }
        //센 소수의 개수 반환
        return count;
    }

}

https://coding-grandpa.tistory.com/81

이 분 내용으로 풀었다,, 사실 부끄럽지만 전 아직도 재귀가...넘넘 어려워용... 유튜브 댓글에 재귀 동작과정 올려두셨던데 이해 안되면 참고~.~

1 > 17은 이해했는데 7을 어떻게 고르지...?라고 고민하고 있었는데 이게 재귀라는 사실을 내가 잊고있었던 것 정신차려!!!!!!!!!!!