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

문제

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

풀이

백트래킹 방법으로 글자 하나 추가한다음, 다음 index로 넘어가면 된다. 그리고 글자 하나를 빼는 방법으로 풀이해주면 된다.

코드

import java.util.*;

class Solution {
     int answer;
    boolean []check = new boolean[10];
    ArrayList<Integer> arr = new ArrayList<>();
    void dfs(String str, String tmp, int m){
        if(tmp.length() == m){
            int num = Integer.parseInt(tmp);
            if(!arr.contains(num))
                arr.add(num);
            return;
        }
        else{
            for(int i=0;i<str.length();i++){
                if(!check[i]){
                    check[i] = true;
                    tmp += str.charAt(i);
                    dfs(str, tmp, m);
                    check[i] = false;
                    tmp = tmp.substring(0, tmp.length()-1);//마지막 글자 하나 뺀다.
                }
            }
        }
    }
    //소수 체크 방법
    void is_prime(int n){
        if(n==0) return;
        if(n==1) return;
        for(int i=2;i< n ;i++){
            if(n % i == 0) return;
        }
        answer++;
    }
    public int solution(String numbers) {
        String tmp ="";
        for(int i=0;i<numbers.length();i++){
            dfs(numbers,tmp,i+1);
        }
        for(int i=0;i<arr.size();i++){
            is_prime(arr.get(i));
        }
        return answer;
    }
}