[JAVA] 소수 찾기 LV.2

< 풀이 >

import java.util.*;
class Solution {
    static HashSet<Integer> set = new HashSet<>(); //중복된 값을 저장하지 않는 hashset
    static void recursive(String comb, String others){ //모든 경우의 수를 찾아주는 함수 
        if(comb!=""){
            set.add(Integer.parseInt(comb));
        }
        
        for(int i=0;i<others.length();i++){
            recursive(comb+others.charAt(i),others.substring(0,i)+others.substring(i+1));
        }
    }
    static boolean isPrime(int num){ //소수인지 아닌지 판별해주는 함수 
        boolean prime=true;
        
        if(num<=1)
            prime=false;
        
        for(int i=2;i<=Math.sqrt(num);i++){
            if(num%i==0) {
                prime =false;
                break;
            }
        }
        
        return prime;
    }
    public int solution(String numbers) {
        recursive("",numbers);
        int answer = 0;
        
        for(int n:set){
            if(isPrime(n)){ //소수이면 
                answer++;
            }
        }
        
        return answer;
    }
}

 

✏️ 풀이 방법

 

1. 재귀 함수에 값을 전달해준다.

2. 재귀 함수에서 전달받은 문자열로 조합해서 만들 수 있는 모든 경우의 수를 구한다. 

    => others 의 길이만큼 substring 함수를 통해 계속 문자열을 잘라가면서 recursive 함수를 계속 호출한다. 

    => 조합된 comb 변수를 정수형으로 변환하여 중복을 허용하지 않는 HashSet에 저장한다.

         ( 정수형으로 저장하지 않으면 011 과 11을 다른 것으로 판단하므로 Integer.parseInt 를 꼭 해서 저장해줘야 함 ! )

3. HashSet 을 돌면서 소수인지 아닌지를 판단하는 isPrime 함수에 값을 전달해준다. 

4. 해당 값이 소수이면 answer의 값을 증가시킨다. 

재귀를 이해하기 위한 나의 노력 ,,

✍🏻 느낀점

 

재귀는 항상 헷갈린다..! 그래도 이렇게 손으로 직접 쓰면서 하니까 이해를 했다. 이 문제는 처음에 봤을 때는 간단한 줄 알았는데, 모든 경우의 수를 구하는 것이 어떻게 해야할지 몰라 어려웠다.. 그래서 유튜브 강의를 찾아봤는데 너무 자세히 설명해주셔서 이해가 됐다. HashSet에 대해서도 더 배우고, 재귀함수를 어떻게 사용하는지에 대해서도 배운 문제였다. 오늘 배운 걸 까먹지 말자,, 다음에 비슷한 문제가 나오면 틀리지 말자,, 

 

 

 

 

 

 

 

참고 자료

---

https://www.youtube.com/watch?v=pF368QqdQb4&t=628s  // 유튜브 강의

https://m.blog.naver.com/sosow0212/222683674446 // 자세한 주석이 있는 블로그