프로그래머스 | 소수 찾기 (Java)

🔒문제

프로그래머스 Lv.2 완전탐색 소수 찾기

🔑해결

한 자리 숫자가 적힌 종이조각들의 문자열 numbers가 주어졌을 때, 종이 조각으로 만들 수 있는 소수가 몇 개인지 return 하는 solution 함수를 작성하는 문제이다.

재귀함수를 사용해 만들 수 있는 모든 경우의 수의 수를 조합하고, 에라토스테네스의 체를 통해 소수를 판별하여 Hashset에 담아 중복을 제거한 소수의 갯수를 구한다.

🔓코드

import java.util.HashSet;
class Solution {
    HashSet<Integer> set = new HashSet<>();
    
    public int solution(String numbers) {
        int answer = 0;
        
        // 숫자 생성
        recursive("", numbers);

        answer = set.size();
        
        return answer;
    }
    
    public void recursive(String comb, String others) {
        if (!comb.equals("")) {
            int number = Integer.parseInt(comb);
            if (!set.contains(number) && is_Prime(number)) {
                set.add(number);
            }
        }

        // 새로운 조합 생성
        for (int i = 0; i < others.length(); i++) {
            recursive(comb + others.charAt(i), others.substring(0, i) + others.substring(i+1));
        }
    }

    private boolean is_Prime(int n) {
        if (n == 0 || n == 1) {
            return false;
        }

        for (int i = 2; i * i <= n; i++) {
            if (n % i == 0) {
                return false;
            }
        }
        return true;
    }
}