[알고리즘] 소수찾기

완전탐색

프로그래머스 레벨2 소수 찾기 문제이다.

완전탐색은 dfs 와 비슷한 방식인듯 싶기도 한데, 익숙해지려면 좀 더 많은 문제를 풀어봐야 겠다.

 

풀이

1. 재귀 함수를 통해 완전 탐색하여 만들 수 있는 모든 숫자를 int 로 변환한다.
2. 각 숫자를 소수 판별하여 소수일 경우 set 에 추가한다. (각 숫자의 제곱근까지만 약수의 여부 검증)
3. set 의 사이즈가 이 문제의 답

최종 코드

import java.util.*;
class Solution {
    Set<Integer> set = new HashSet<>();
    
    // 소수 판별 메서드
    public boolean isPrime(int item) {
        if (item <= 1) {
            return false;
        }
        int limit = (int) Math.sqrt(item);
        for (int i = 2; i <= limit; i++) {
            if (item % i == 0) {
                return false;
            }
        }
        return true;
    }
    
    // 재귀 함수
    public void reculsive(String start, String rest) {
        if (!start.equals("")) {
            int item = Integer.parseInt(start);
            // 소수 판별
            if (isPrime(item)) {
                set.add(item);
            }
        }
        for (int i = 0; i < rest.length(); i++) {
            reculsive(start + rest.charAt(i), 
                rest.substring(0, i) + rest.substring(i+1));
        }
    }
    
    public int solution(String numbers) {
        reculsive("", numbers);
        return set.size();
    }
}