[프로그래머스 Level2] 소수 찾기 (JAVA)

[문제]

출처 - https://programmers.co.kr/learn/courses/30/lessons/42839?language=java 

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

---

[문제 풀이]

이 문제는 소수를 판단하는 함수와 dfs방식으로 찾는 함수를 만들어서 구현을 해준다.

dfs함수를 구현할때 String 값을 Integer값으로 변경하여 찾을 수 있는 값 전부를 중복없이 리스트에 담아주고

리스트에 담긴 값들을 소수판단하여 세주면 된다.

• 백트래킹 방법 사용
• for문을 사용해 각 1부터 ~ numbers 의 길이만큼 순열을 만들어 준다. 
• ArrayList을 만들어  순열을 만드는데 11과 011과 같은 중복되는 수는 중복을 체크하고 리스트에 넣어준다.
• 리스트에 담긴 모든 값을 소수인지 아닌지 판단한다.

---

[소스 코드]

import java.io.*;
import java.util.*;
class Solution {
    static ArrayList<Integer> arr = new ArrayList<>();
    static boolean[] check = new boolean[7];
    
    public int solution(String numbers) {
        int answer = 0;
        for(int i=0; i<numbers.length(); i++){
            dfs(numbers,"",i+1);
        }
        
        for(int i=0; i<arr.size(); i++){
            if(prime(arr.get(i))) answer++;              
        }
        
        return answer;
  
    }
	//백트래킹
	static void dfs(String str, String temp, int m) {
            if(temp.length() == m){
                int num = Integer.parseInt(temp);
                if(!arr.contains(num)){
                    arr.add(num);
                }
            }
        
            for(int i=0; i<str.length(); i++){
                if(!check[i]){
                    check[i] = true;
                    temp += str.charAt(i);
                    dfs(str, temp, m);
                    check[i] = false;
                    temp = temp.substring(0, temp.length()-1);
                }
            }
		
	}
	//소수 판단
	static boolean prime(int n) {
		if(n<2) return false;
		
		for(int i=2; i*i<=n; i++) {
			if(n % i == 0) return false;
		}
		
		return true;
	}

}