[Algorithm/Java][프로그래머스] 소수 찾기

[프로그래머스] 소수 찾기

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

문제 접근

String으로 들어오는 숫자들로 가능한 모든 숫자 조합을 만들고 이 숫자중세서 소수를 찾는 문제이다.
소수를 찾기위해서 Math.sqrt(n)을 이용해서 반복문 횟수를 줄이고, dfs를 이용해서 모든 경우의 수를 탐색하였다.
그리고 같은 숫자가 두개 이상있으면 중복되는 숫자들이 나타나게 되어서 HashSet을 이용해서 중복 경우의 수를 제거하였다.

Code

import java.util.HashSet;
class Solution {
    char[] nums;
    boolean[] visited;
    HashSet<Integer> hs = new HashSet<>();
    public int solution(String numbers) {
        nums = new char[numbers.length()];
        visited = new boolean[numbers.length()];
        for(int i = 0 ; i<numbers.length(); i++){
            nums[i] = numbers.charAt(i);
        }
        dfs("");
        return hs.size();
    }

    void dfs(String str){
        if(str.length() != 0){
            int num = Integer.parseInt(str);
            if(isPrime(num)) {
                hs.add(num);
            }
        }
        for(int i = 0; i<nums.length; i++){
            if(!visited[i]){
                if(str.length() == 0 && nums[i] == '0') continue;
                visited[i] = true;
                dfs(str+nums[i]);
                visited[i] = false;
            }
        }

    }

    boolean isPrime(int n){
        if(n==0 || n==1) return false;
        for(int i = 2; i<=Math.sqrt(n); i++){
            if(n%i == 0) return false;
        }
        return true;
    }
}

어려웠던 점 / 배운 점 / 느낀 점

011이 입력으로 들어오게 되면 11 101이 두번씩 조합이 될 수 있기때문에 중복 문제를 해결하기 위해서 HashSet을 이용하게 되었다.
그리고 이전까지 풀었던 문제들은 011이라면 str의 길이가 3일때까지 간 다음에 판별하는 문제들이였는데, 이렇게 하니까 1이나 10 같은 1,2의 길이를 가진 숫자들은 건너뛰는 문제가 발생했다. 같은 알고리즘이여도 문제가 엄청 다양하다...후...