[프로그래머스] 소수 찾기(Java, 자바)

문제

소수 찾기

📌 아이디어

이 문제는 요구사항에 맞게 숫자를 생성하는 메소드와 소수를 검증하는 메소드 2개를 만들어 해결했습니다.

1. 먼저 숫자를 생성하는 메소드는 백트래킹을 활용했습니다.
2. 탐색을 진행하면서 문자열의 길이가 1이상이라면 문자열을 숫자로 변환합니다.
3. 변환한 숫자는 중복을 고려하여 Hash Set에 추가합니다.
4. 추가한 숫자들은 소수 여부를 검증합니다.
5. 소수는 2부터 N까지의 제곱근까지 탐색하여 나누어 떨어지면 소수가 아니므로 메소드를 종료하고 아니라면 카운트하여 정답을 처리합니다.

📌 코드

import java.util.*;

class Solution {
    static int cnt = 0;
    static HashSet<Integer> nums = new HashSet<>();
    static int[] check = {};
    
    public int solution(String numbers) {
        int answer = 0;
        check = new int[numbers.length()];
        
        dfs(numbers, check, "");
        
        for(int num : nums){
            primeNumber(num);
        }
        
        answer = cnt;
        return answer;
    }
    // 생성 가능한 숫자 만들기
    static void dfs(String numbers, int[] check, String tmp) {
        // 길이가 1이상이면 해쉬셋에 추가
        if (tmp.length() >= 1){
            int tmpNum = Integer.parseInt(tmp);
            nums.add(tmpNum);
        }
        
        for (int i=0; i<numbers.length(); i++){
            // 체크가 아니라면 탐색 진행
            if (check[i] == 0){
                check[i] = 1;
                tmp += numbers.charAt(i);
                dfs(numbers, check, tmp);
                tmp = tmp.substring(0, tmp.length()-1);
                check[i] = 0;
            }
        }
    }
    // 소수 찾기
    static void primeNumber(int n){
        // 0과 1은 소수가 아님
        if(n == 0) return;
        if(n == 1) return;
        
        // 2부터 N까지의 제곱근까지 돌면서 나누어 떨어지면 소수가 아니므로 메소드 종료.
        for(int i=2;i<=Math.sqrt(n);i++){
            if(n % i == 0) return;
        }
        
        // 모두 나누어 떨어지지 않으면 소수이므로 answer 증가.
        cnt++;
            
    }
}

피드백 및 개선점은 댓글을 통해 알려주세요😊