[JAVA] 프로그래머스 : 소수 찾기 (코딩테스트 고득점 kit > 완전탐색)

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

코딩테스트 연습 - 소수 찾기

재귀호출을 이용하여 완전탐색하였음

해결 방안

1. 주어진 Numbers를 이용하여 만들 수 있는 전체 숫자의 경우를 구함
이 때, 만들어지는 숫자는 순열로 1~N자리의 숫자를 생성할 수 있으므로 nP1 ~ nPn 까지의 전체 숫자를 구해줌

2. 전체의 숫자를 구하면서 nPr의 r만큼의 숫자가 누적되어 만들어지면 중복 판단 및 소수 판단을 하고 소수이면 answer++을 해줌
소수 판단은 아리스토테네스의 체 방법을 이용하여 구현함

 

코드

import java.util.*;

// 소수 찾기
class Solution {
    // 소수 갯수
    public static int answer;
    // 중복되지 않는 전체 숫자 저장
    public static Set<Integer> totalNumbers; 
    
    public int solution(String numbers) {
        answer = 0;
        
        totalNumbers = new HashSet<>();
        int[] numbersArr = new int[numbers.length()];
        boolean[] usedNumbers = new boolean[numbers.length()];
        
        for(int i=0; i<numbersArr.length; i++){
            numbersArr[i] = Integer.parseInt(numbers.charAt(i) + "");
            usedNumbers[i] = false;
        }
        
        // 전체 숫자의 경우 구하기 (nP1 ... ~ nPn)
        // r : 1 ~ n
        for(int r=1; r<=numbersArr.length; r++){
            getResult(numbersArr, usedNumbers, "", r, 0);
        }
        
        return answer;
    }
    
    public static void getResult(int[] numbersArr, boolean[] usedNumbers, String num, int r, int current){
        
        // current번째 for문
        if(current >= r){
            // 숫자를 totalNumbers에서 있는지 Integer형으로 찾아봄(중복 확인)
            // 없으면 저장하고 숫자가 소수인지 판단
            if(!totalNumbers.contains(Integer.parseInt(num))){
                totalNumbers.add(Integer.parseInt(num));
                
                // 소수 판단
                if(isPrime(Integer.parseInt(num))){
                    answer++;
                    //System.out.println(num);
                }
                    
            }
            return;
            
        }
        else{
            for(int i=0; i<numbersArr.length; i++){
                //System.out.println(current+ ": " + i + ", " + numbersArr[i] );
                if(!usedNumbers[i]){
                    num += Integer.toString(numbersArr[i]);
                    usedNumbers[i] = true;
                    getResult(numbersArr, usedNumbers, num, r, current+1);
                    usedNumbers[i] = false;
                    num = num.substring(0, num.length()-1);
                }
                
            }
        }
    }
    
    public static boolean isPrime(int num){
		int sqrt = (int) Math.sqrt(num);

		// 2는 유일한 짝수 소수
		if (num == 2)
			return true;

		// 짝수와 1은 소수가 아님
		if (num % 2 == 0 || num == 1)
			return false;

		// 제곱근까지만 홀수로 나눠보면 됨
		for (int i = 3; i <= sqrt; i += 2) {
			if (num % i == 0)
				return false;
		}

		return true;
    }
}