[Java] 소수 찾기

https://school.programmers.co.kr/learn/courses/30/lessons/42839

스스로 풀지 못한 문제
파이썬과 달리 자바에선 조합 라이브러리가 없어서 숫자 조합의 로직을 구성하는데 어려웠음.

import java.util.*;

class Solution {
    HashSet<Integer> set = new HashSet<>();
    
    // 소수 체크
    public boolean isPrime(int num){
        // 1. 0과 1은 소수가 아님
        if(num == 0 || num ==1){
            return false;
        }
        // 2. 에라토스테네스의 체 limit 계산
        int limit = (int)Math.sqrt(num); // 루트 씌운 값까지 계산
        
        // 3. 에라토스 체에 따라 limit까지만 배수 여부 확인
        for(int i=2; i<limit + 1; i++){
            if(num % i == 0)
                return false;
        }
        return true;
    }
    
    public void makeNum(String comb, String others){
        // 1. 현재 조합을 set에 추가
        if(!comb.equals(""))
            set.add(Integer.valueOf(comb));
        
        for(int i=0; i<others.length(); i++){
            // 2.남은 숫자 들 중 하나를 더해 새로운 조합 만듦.
            makeNum(comb+others.charAt(i), others.substring(0,i) + others.substring(i+1));
        }
    }
    
    public int solution(String numbers) {
        int answer = 0;
        
        // 1. 숫자 조합 만들기 -> 재귀 사용
        makeNum("", numbers);
                
        // 2. 소수 개수 세기
        Iterator<Integer> iter = set.iterator();
        
        int cnt = 0;
        while(iter.hasNext()){
            int number = iter.next();
            
            if(isPrime(number))
                cnt ++;
        }
        
        // 3. 소수 개수 반환
        return cnt;
    }
}

알고리즘

1. 숫자 조합을 만든다: 재귀함수 사용

• 중복 조합을 없애기 위해: set 활용
• 현재까지 만들어진 조합을 set에 추가함
• 다음 조합을 위해: 현재 숫자 + 다음 숫자 문자열(substring)

2. 조합 중 소수의 개수만 세기

• 에라토스의 체의 개념을 활용해 (숫자)의 제곱수까지만 체크하도록 for문의 limit을 건다
• 이때, 0,1는 소수가 아님
• Interator 인터페이스를 사용해 set을 순회(hasNext(), next())