[Programmers] 소수 찾기

코딩테스트 연습 - 소수 찾기

---

[DFS + 백트래킹]

입력으로 들어온 문자열을 한 글자씩 쪼개어 char[] 에 저장하고, 각 인덱스에 해당하는 문자마다 방문했는지를 체크하기 위한 boolea[] visit를 준비했다.

 

즉 "017" 이라는 문자열이 있을 때 0은 0번째, 1은 1번째, 7은 2번째로 , 0을 포함하고 있다면 visit[0] = true가 되고, 0을 포함한 채로 1을 포함하고 있다면 visit[0]과 visit[1] 은 참이 된다.

 

백트래킹을 이용했기 때문에 DFS 끝나는 부분에서는 사용했던 전역 변수를 다시 원래대로 되돌려놓는다.

 

소수인지 판별법은 isPrime() 메서드를 참고한다.

# Code </>

class Solution {

    static char[] str;
    static int count = 0, len;
    static boolean[] check = new boolean[10000000];
    static boolean[] visit = new boolean[8];

    static boolean isPrime(int x){

        if(x == 1 || x == 0) return false;

        for(int i=2; i <= Math.sqrt(x); i++)
            if(x % i == 0)
                return false;

        return true;
    }

    static void DFS(int cur, StringBuilder num_){

        visit[cur] = true;

        num_.append(str[cur]);
        int num = Integer.parseInt(num_.toString());

        if(!check[num]){
            check[num] = true;

            if(isPrime(num))
                count++;
        }

        for(int i=0; i<len; i++)
            if(!visit[i])
                DFS(i, new StringBuilder(num_));

        visit[cur] = false;
    }

    public int solution(String numbers) {

        str = numbers.toCharArray();
        len = str.length;

        for(int i=0; i<len; i++)
            if(!visit[i])
                DFS(i, new StringBuilder());

        return count;
    }
}