# 20. 소수 찾기_완전탐색 | 프로그래머스 (JAVA) | Brute-Force | Exhaustive Search

# 🔒 문제 (opens new window)

한자리 숫자가 적힌 종이 조각이 흩어져있습니다. 흩어진 종이 조각을 붙여 소수를 몇 개 만들 수 있는지 알아내려 합니다.

각 종이 조각에 적힌 숫자가 적힌 문자열 numbers가 주어졌을 때, 종이 조각으로 만들 수 있는 소수가 몇 개인지 return 하도록 solution 함수를 완성해주세요.

# 📢 제한사항

numbers는 길이 1 이상 7 이하인 문자열입니다.
numbers는 0~9까지 숫자만으로 이루어져 있습니다.
"013"은 0, 1, 3 숫자가 적힌 종이 조각이 흩어져있다는 의미입니다.

# 📢 입출력 예

numbers	return
"17"	3
"011"	2

# 📢 입출력 예 설명

입출력 예 #1
- [1, 7]으로는 소수 [7, 17, 71]를 만들 수 있습니다.
입출력 예 #2
- [0, 1, 1]으로는 소수 [11, 101]를 만들 수 있습니다.
  - 11과 011은 같은 숫자로 취급합니다.

# 🔐

💡

만들 수 있는 숫자 조합을 만든다.
소수인지 확인한다.

해당 링크 (opens new window)를 참고하여 풀었다..

# 🔑 풀이

import java.util.HashSet;
import java.util.Iterator;

class Solution {
    HashSet<Integer> numbersSet = new HashSet<>(); // 숫자 조합 Set
    
    public int solution(String numbers) {
        // 1. 만들 수 있는 숫자 조합 모두 만들기
        recursive("", numbers);

        int answer = 0;

        Iterator<Integer> itr = numbersSet.iterator();
        while(itr.hasNext()) {
            int num = itr.next();
            if (checkNum(num))
                answer++;
        }
        return answer;
    }
    
     // 모든 숫자 조합 만들기
    public void recursive(String num, String oth) {
        // set 추가
        if (!num.equals("")) {
            numbersSet.add(Integer.valueOf(num));
        }

        // 기존 숫자(n)에 남은 숫자(oth)를 조합하여 새로운 숫자를 만든다.
        for (int i=0; i < oth.length(); i++) {
            recursive(num + oth.charAt(i), oth.substring(0, i) + oth.substring(i+1));
        }
    }

    // 소수 확인
    public boolean checkNum(int num) {
        // 0과 1 은 소수가 아니다
        if (num == 0 || num == 1) {
            return false;
        }

        // 제곱근 구하기
        int lim = (int)Math.sqrt(num);

        // 배수 여부 확인 (나눠서 0이 나올경우 소수 X)
        for (int i=2; i<=lim; i++) {
            if (num%i == 0)
                return false;
        }
        return true;
    }
}