소수 찾기(Lv.2)

 

---

 

문제 설명

 

 

 

입출력 예시

 

 

요약

주어진 숫자로 조합해서 만든 숫자가 소수인지 판별

 

---

 

풀이

 

문제 해석

각 숫자로 만들 수 있는 모든 숫자 만들어서 소수인지 판별

 

 

접근 방식

1. 모든 숫자 조합 구하기

  → 순열에 가까운 조합방식으로 재귀함수를 통해 숫자 조합을 구한다.

 

2. 소수 판별

  → 0과 1을 제외한 숫자 중, 2 ~ (해당 숫자-1)과 나눴을 때 나머지가 0이면 소수가 아님

  → '에라토스테네스의 체'를 통해 해당 숫자의 제곱근까지만 반복문 실행

 

---

 

코드리뷰

 

import java.util.*;

class Solution {
    HashSet<Integer> set = new HashSet<>();
    public boolean isPrime(int num) {	// 소수인지 판별하는 메소드
        boolean result = true;
        int limit = (int)Math.sqrt(num);	// 제곱근 구하기
        if(num == 0 || num == 1) {	// 0과 1 제외
            result = false;
        } else {
            for(int i = 2; i <= limit; i++) {	// 2부터 제곱근까지 나눗셈 실행
                if(num % i == 0) {
                    result = false;	// 나머지가 0인 경우 소수아님
                }
            }
        }
        return result;
    }
    public void dfs(String combination, String remains) {	// 모든 숫자 조합 구하는 메소드(재귀함수)
        if(!combination.isBlank()) {
            set.add(Integer.valueOf(combination));	// set에 담아서 중복을 제거
        }
        for(int i = 0; i < remains.length(); i++) {
        	// i번째 숫자를 떼서 첫 번째 인자로 넘기고, i번째 숫자를 제외하고 나머지를 붙여서 두 번째 인자로 넘겨준다.
            dfs(combination + remains.substring(i, i+1), remains.substring(0, i) + remains.substring(i+1));
        }
    }
    public int solution(String numbers) {
        int answer = 0;
        dfs("", numbers);	// 재귀함수 호출
        Iterator<Integer> it = set.iterator();	// iterator 반복자를 통해 비교
        while(it.hasNext()) {
            int num = it.next();
            if(isPrime(num)) {	// 소수 판별 메소드 호출
                answer++;	// 소수의 개수 증가
            }
        }
        return answer;
    }
}

 

 

 

* refs

https://www.youtube.com/watch?v=pF368QqdQb4&list=PLlV7zJmoG4XI9VguUVNMu3pCjssb4aR_0&index=3