소추 찾기(JAVA)

문제

프로그래머스

String형으로 주어진 숫자를 조합하면서 소수의 개수를 찾는 문제이다.

1. 먼저 소수를 판별을 하기 위해 에라토스테네스의 체를 사용했다.

public void prime(){
        for(int i=0;i<100000000;i++){
            arr[i]=0;
        }
        for(int i=2;i<arr.length;i++){
            if(arr[i]==i)continue;
            arr[i]=1;
            for(int j=i+i;j<arr.length;j+=i)
                arr[j]=j;
        }
    }

2. 순열을 돌면서 소수인지 확인하는 dfs을 구현

public void dfs(String s, int idx){
        if(s != ""){
            if(arr[Integer.parseInt(s)]==1){
                set.add(Integer.parseInt(s));            
            }
        }
        if(idx == ch.length)return;
        for(int i=0;i<ch.length;i++){
            if(visited[i])continue;
            visited[i]=true;
            dfs(s+ch[i], idx+1);
            visited[i]=false;
        }
    }

set은 Hashset이므로 중복된 소수를 알아서 처리해준다.

visitied 배열은 boolean형으로 순열의 백트래킹 기법에 사용된다.

ch는 입력으로 들어온 숫자의 길이이므로 idx가 ch의길이와 같게 되면 전부 순회한것이다.

처음에 String s는 "" 으로 들어온다.

---

전체 코드이다.

import java.util.*;
class Solution {
    int [] arr = new int[100000000];
    char[] ch;
    boolean[] visited;
    HashSet<Integer>set = new HashSet<>();
    public int solution(String numbers) {
        int answer = 0;
        prime();
        ch = new char[numbers.length()];
        visited = new boolean[numbers.length()];
        for(int i=0;i<numbers.length();i++)
            ch[i] = numbers.charAt(i); //i번째 인덱스를 char형으로변환
        dfs("", 0);
        answer = set.size();
        return answer;
    }
    public void dfs(String s, int idx){
        if(s != ""){
            if(arr[Integer.parseInt(s)]==1){
                set.add(Integer.parseInt(s));            
            }
        }
        if(idx == ch.length)return;
        for(int i=0;i<ch.length;i++){
            if(visited[i])continue;
            visited[i]=true;
            dfs(s+ch[i], idx+1);
            visited[i]=false;
        }
    }
    public void prime(){
        for(int i=0;i<100000000;i++){
            arr[i]=0;
        }
        for(int i=2;i<arr.length;i++){
            if(arr[i]==i)continue;
            arr[i]=1;
            for(int j=i+i;j<arr.length;j+=i)
                arr[j]=j;
        }
    }
}