99클럽 코테 스터디 23일차 TIL 완전탐색(소수찾기)

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

프로그래머스

 

<아이디어>

주어진 수를 가지고 만들 수 있는 모든 자릿수의 소수를 구하는 문제이다.

모든 자릿수를 구하기위해 부분집합을 사용했고,

이 자릿수로 만들 수 있는 모든 순서를 구하기위해 순열을 사용했다.

그리고 각각의 수를 소수판별을 해서 소수는 set에 넣어주고, 마지막엔 set의 사이즈를 리턴했다. (중복 제거 위해)

 

<문제>

그리고 제출했으나, 2/10/11/12번 테케가 틀렸다.

이유는 소수 판별을 할 때 Math.sqrt(num) 범위까지의 수로만 판별해서 121과 같은 소수의 제곱수를 판별하지 못해서였다.

따라서 Math.sqrt(num)+1 까지로 범위를 변경해주니 통과할 수 있었다.

 

<제출코드>

import java.util.*;

class Solution {
    
    static int len;
    static int answer;
    static boolean[] select1;
    static boolean[] select2;
    static HashSet<Integer> set;
    
    // 소수 판별 메서드
    public static boolean isPrime(int num){
        if(num < 2) return false;
        for(int i=2; i<(int)Math.sqrt(num)+1; i++){
            if(num % i == 0) return false;
        }
        set.add(num);
        return true;
    }
    
    // 숫자 순열
    public static void permu(int cnt, String[] arr, String[] input, int N){
        if(cnt == N){
            StringBuilder sb = new StringBuilder();
            for(int i=0; i<N; i++){
                sb.append(input[i]);
            }
            if(sb.length() != 0) isPrime(Integer.parseInt(sb.toString()));
            return;
        }
        for(int i=0; i<N; i++){
            if(select2[i]) continue;
            input[cnt] = arr[i];
            select2[i] = true;
            permu(cnt+1, arr, input, N);
            select2[i] = false;
        }
    }
    
    // 숫자 부분집합
    public static void subset(int cnt, String numbers, int total){
        if(cnt == len){
            String[] arr = new String[total];
            int idx = 0;
            for(int i=0; i<len; i++){
                if(select1[i]) arr[idx++] = numbers.substring(i, i+1);
            }
            select2 = new boolean[total];
            String[] input = new String [total];
            permu(0, arr, input, total);
            return;
        }
        select1[cnt] = true;
        subset(cnt+1, numbers, total+1);
        select1[cnt] = false;
        subset(cnt+1, numbers, total);
    }
    
    public int solution(String numbers) {
        
        len = numbers.length();
        select1 = new boolean[len];
        set = new HashSet<>();
        subset(0, numbers, 0);
        
        return set.size();
    }
}