[프로그래머스]레벨2- 소수 찾기 [JAVA, 자바]

문제 설명

한자리 숫자가 적힌 종이 조각이 흩어져있습니다. 흩어진 종이 조각을 붙여 소수를 몇 개 만들 수 있는지 알아내려 합니다.

각 종이 조각에 적힌 숫자가 적힌 문자열 numbers가 주어졌을 때, 종이 조각으로 만들 수 있는 소수가 몇 개인지 return 하도록 solution 함수를 완성해주세요.

풀이 방법

• 백트래킹으로 numbers로 구할 수 있는 모든 숫자를 구한다.(조합)
• 구한 숫자들을 소수인지 판별한다.
• 백트래킹 개념이 잡혀있지 않다면, https://youtu.be/Enz2csssTCs 바킹독님의 백트래킹 강의를 들어보는 것이 좋다.
• 백준 사이트의 n과 m을 풀어보면서 백트래킹을 익혀보자 !

알아야되는 개념

• 백트래킹
• 소수 판별 알고리즘

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;
    }
}