코딩테스트 연습 > 완전탐색 > 소수 찾기

이전 코드

import java.util.*;

class Solution {
    ArrayList<Integer> allIntArray = new ArrayList<>();

    public int solution(String numbers) {
    
        int answer = 0;
        
        int length = numbers.length();
        int[] arr = new int[length];;
        char[] cArray = numbers.toCharArray();
        
        for (int i = 0 ; i < cArray.length ; i++){
            arr[i] = Integer.parseInt(String.valueOf(cArray[i]));
        }
        
        for (int i = 1 ; i <= length ; i ++) {
            per(arr, 0, length, i);
        }
        
        for (int num : allIntArray){
            if (num != 1 && num != 0){
                boolean isNumPrime = true;

                for(int i = (int)Math.sqrt(num) ; i >= 2 ; i--){
                    if(num % i == 0){
                        isNumPrime = false;
                        break;
                    }
                }

                if(isNumPrime){
                    answer ++;
                }
            }
        }
        
        return answer;
    }
    
    

    public void per(int[] intArray, int depth, int n, int r) {
        if(depth == r) {
            StringBuilder sb = new StringBuilder("");
            for(int i = 0; i < r; i++)
                sb.append(intArray[i]);
            if(!allIntArray.contains(Integer.parseInt(sb.toString()))){
                allIntArray.add(Integer.parseInt(sb.toString()));
            }
            return;
        }

        for(int i = depth; i < n; i++) {
            swapNum(intArray, depth, i);
            per(intArray, depth + 1, n, r);
            swapNum(intArray, depth, i);
        }
    }

    static void swapNum(int[] arr, int depth, int i) {
        int temp = arr[depth];
        arr[depth] = arr[i];
        arr[i] = temp;
    }
    
}

최근 코드

import java.util.*;

class Solution {
    static HashMap <Integer, Integer> map = new HashMap<>();
    public int solution(String numbers) throws Exception {
        int answer = 0;
        
        int [] array = new int[numbers.length()];
        for (int i = 0 ; i < numbers.length() ; i ++){
            array[i] = Integer.parseInt(String.valueOf(numbers.charAt(i)));
        }
        
        for (int i = 1 ; i <= numbers.length() ; i++){
            getAllNum(array, 0, numbers.length(), i);
        }
        for (Integer key : map.keySet()){
            if (key != 0 && key != 1){
                boolean isPrime = true;
                
                for (int i = (int) Math.sqrt(key) ; i >= 2 ; i--){
                    if (key % i == 0){
                        isPrime = false;
                        break;
                    }
                }
                if(isPrime){
                    answer ++;
                }
            }
        }
        
        return answer;
    }
    
    public static void getAllNum(int [] array, int depth, int n, int r) throws Exception{
        if (depth == r){
            StringBuilder sb = new StringBuilder();
            for (int i = 0 ; i < r ; i ++){
                sb.append(array[i]);
            }
            map.put(Integer.parseInt(sb.toString()), 0);
            return;
        }
        
        for (int i = depth ; i < n ; i++){
            swapNum(array, depth, i);
            getAllNum(array, depth + 1, n, r);
            swapNum(array, depth, i);

        }
    }
    
    public static void swapNum(int [] arr, int depth, int i){
        int temp = arr[depth];
        arr[depth] = arr[i];
        arr[i] = temp;
    }
}