[programmers] 소수찾기

문제 풀이 : 2021.05.03

풀이

주어진 숫자들로 모든 조합을 만들어야 함 -> 완전탐색
만들어진 조합이 소수인지 판별 후 list에 넣음 -> 중복 체크
소수 판별할 때 제곱근도 포함 시켜야 함
조합 한 숫자가 0, 1, 0이 여러개 일 경우 예외처리

코드

import java.util.*;
class Solution {
    static char[] n;
    static boolean[] used;
    static ArrayList<Integer> list = new ArrayList<>();
    
    public int solution(String numbers) {
        int answer = 0;
        n = numbers.toCharArray();
        for(int i = 1 ;i<numbers.length()+1;i++){
            char[] tmp = new char[i];
            used = new boolean[numbers.length()];
            makeNum(0,i,tmp);
        }

        answer = list.size();
        return answer;
    }
    
    static void makeNum(int a, int length, char[] b){
            if(a == length){
                int t = Integer.parseInt(String.valueOf(b));
                if(t==0) return;
                if(!list.contains(t) && isPrime(t))
                    list.add(t);
            }
        else{
            for(int i = 0;i<n.length;i++){
                if(!used[i]){
                    used[i] = true;
                    b[a] = n[i];
                    makeNum(a+1, length, b);
                    b[a] = 0;
                    used[i] = false;
                }
            }
        }
        return;
    }
    
    static boolean isPrime(int num){
        if(num==1) return false;
        else{
            boolean check = false;
            for (int i = 2; i <= Math.sqrt(num); i++) {
                if (num % i == 0) {
                    check = true;
                    break;
                }
            }
            if(check) return false;
            else return true;
        }
    }
}

문제 출처 링크