[Programmers]-소수 찾기(완전탐색)

문제

귀찮아서 문제는 대충찍어야겠다.

문제 요약

주어진 numbers로 조합을 통해 소수를 찾아서 갯수를 리턴하면된다.

코드

import java.util.*;

class Solution {
    static boolean[] visited;//방문여부 배열
    static boolean[] notPrime;//소수인지 판별 배열
    
    static HashSet<Integer> arr = new HashSet<Integer>();//조합을 담을 set
    
    public static void rec(String numbers, String temp, int len){//numbers,임시문자열,자리수
        
        if(temp.length() == len){//자리수에 맞아졌는가 조건문
            arr.add(Integer.parseInt(temp));//맞으면 set에 추가
        }
        
        for(int j=0;j<numbers.length();j++){//각자리수 찾아가며
            
            if(visited[j]) continue;//방문시 넘어가기
            
            temp += numbers.charAt(j);//방문 안했으니 임시문자열에 추가
            visited[j] = true;//방문표시
            rec(numbers, temp, len);//재귀
            visited[j] = false;//재귀빠져나왔으니 방문풀어주고
            temp = temp.substring(0,temp.length()-1);//임시값도 재귀에서 빠졌으니 추가했던거 빼준다.
        }
    }
    
    static void isPrime(int max){//notPrime==false 소수이다.
        notPrime = new boolean[max+1];//
        notPrime[1] = true;
        
        for(int i=2; i<=max/2; i++)
            for(int j=2; i*j<=max; j++)
                notPrime[i*j]= true;
    }
    
    public int solution(String numbers) {
        int answer = 0;
        visited = new boolean[numbers.length()];
        //정렬해주기
        String[] s = numbers.split("");
        numbers="";
        Arrays.sort(s);
        for (String str : s)//numbers는 내림차순 정렬되었다.그러면 최대값이된다.
            numbers = str + numbers;
        
        isPrime(Integer.parseInt(numbers));//배열에 소수인지아닌지 입력
        
        for(int i = 1;i<=numbers.length();i++){//자리수만큼for문
            rec(numbers,"",i);
        }
        
        arr.remove(0);//0이 있으면 지우기
        for(int n : arr){
            if(notPrime[n]==false) answer++;
        }
        
        return answer;
    }
    
}

코드 설명

천천히 흐름을 보며 주석을 보면 알기 쉬워진다.

요약

• 중복을 방지하기 위해 list에서 set으로 변경했다. 순서는 보장 안해줘도 상관없으니
• 에라토스테네스의 체를 이용했는데 굳이 배열에 담을 필요가 없어진거같다. 수가 커질수록 배열크기만 늘기때문에… 그냥 판별 여부만 구해도 될것 같다.
• 처음에 어떡할지 몰랐는데 순열 알고리즘을 보며 이해하고 적용하는 노력했다. 알고나니 쉬운편이었다.