프로그래머스 소수 찾기 - Java

 

링크로 문제설명 대체.

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

프로그래머스

 

*문제해결을 위한 단계

1단계 : input인 String numbers ="17" 일때 이 숫자를 조합해 만들 수 있는 수 중에 소수를 찾는다. "17"일 경우에 소수는 3개로 7, 17, 71 이 있다. 이것은 DFS로 찾는다.

2단계: 소수인지 아닌지 검사하는 함수를 생성한뒤, 소수이면 set 자료형에 add한다. 왜냐하면 set자료형은 중복을 허용안함이기 때문임. 

 

3단계: 소수이고, 중복되지 않는 값만 set 자료형에 추가되었으므로 문제에 대한 return은 set.size() 이다.

- 전체코드 

import java.util.*;
class Solution {
    static int answer = 0;
    static int[] ch;
    static HashSet<Integer> set = new HashSet<>();
    static String [] arr; 
    static int len;
    //소수검사
    public boolean isValid(int num){
        if(num <= 1) return false;
        if(num == 2) return true;
        if(num > 2){
            for(int i=2;i<num;i++) if(num%i==0)return false; 
        }
        return true;
    }
    public void DFS(int l,String temp){
        int num;
        if(!temp.equals("")){
            num = Integer.parseInt(temp);
            if(isValid(num)) set.add(num); // 소수이면 set에 add 
        }
        if(l==len) return;
        else{
            for(int i=0;i<len;i++){
                if(ch[i]==0){
                    ch[i] = 1; 
                    DFS(l+1,temp+arr[i]); 
                    ch[i] = 0; // 백트래킹
                }
            }
        }
    }
    public int solution(String numbers) {  
        len = numbers.length();
        arr = numbers.split("");
        ch = new int[arr.length];
        DFS(0,"");
        answer=set.size();
        return answer;
    }
}