StringBuilder를 활용한 dfs

StringBuilder를 활용한 dfs 알고리즘 풀이(소수 찾기)

public class FindPrimeNumber { // 소수 찾기
    public static void main(String[] args) {
        String numbers = "1231";
        System.out.println(solution(numbers));

    }

    public static int solution(String numbers) {
        HashSet<Integer> hashSet =new HashSet<>();
        boolean[] visited = new boolean[numbers.length()];
        StringBuilder sb = new StringBuilder();
        for(int i=1; i<=numbers.length();i++){
            dfs(numbers,sb,numbers.length(),i,0,visited,hashSet);
        }
        return hashSet.size();
    }

    public static void dfs(String numbers,StringBuilder sb,int n,int r,int depth,boolean[] visited,HashSet<Integer> hashSet){
        if(depth==r){
            int value = Integer.parseInt(sb.toString());
            if(isPrime(value)){
                hashSet.add(value);
            }
            return;
        }

        for(int i=0; i<n;i++){
            if(!visited[i]){
                sb.append(numbers.charAt(i));
                visited[i] = true;
                dfs(numbers,sb,n,r,depth+1,visited,hashSet);
                sb.setLength(depth);
                visited[i] = false;
            }
        }
    }

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

        return true;
    }


}

dfs의 풀이에서 StringBuilder를 사용할 경우 dfs가 끝난 후  StringBuilder의 길이를  depth의 값으로로 제한하면 올바른 정답값을 얻을 수 있다.

 

 

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

프로그래머스