문제 설명

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

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

제한사항

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

입출력 예

Untitled

입출력 예 설명

예제 #1[1, 7]으로는 소수 [7, 17, 71]를 만들 수 있습니다.

예제 #2[0, 1, 1]으로는 소수 [11, 101]를 만들 수 있습니다.

• 11과 011은 같은 숫자로 취급합니다.

시도1. 숫자의 조합을 구하지 않고 시도

→ 모든 숫자의 조합을 구하는 것이 시간이 오래걸린다고 생각하여, 최대 숫자의 조합만 구한 뒤 1~최대숫자 사이의 소수를 구한다.

→ 구한 소수들을 가지고 있는 문자열과 비교하여 일치 검사를 한다.

→ 실패, 중복이 가능한 문자와 불가능한 문자를 구분하지 못한다.

시도2. 숫자의 조합을 재귀 조합을 통해 구함

package programmers.fullsearch;

import java.util.HashSet;
import java.util.Set;

public class Q2 {
    public static void main(String[] args) {
        class Solution {
            public Set<Integer> recursive(String combination, String others, Set<Integer> combinationSet) {
                System.out.println(combination);
                if (!combination.equals("")) {
                    combinationSet.add(Integer.parseInt(combination));
                }
                for (int i = 0; i < others.length(); i++) {
                    recursive(combination + others.charAt(i), others.substring(0, i) + others.substring(i + 1), combinationSet);
                }
                return combinationSet;
            }

            public int solution(String numbers) {
                int answer = 0;
                Set<Integer> combinationSet = new HashSet<>();
                recursive("", numbers, combinationSet);
                System.out.println(combinationSet);

                for (Integer combination : combinationSet) {
                    boolean isPrime = true;
                    for (int i = 2; i < combination; i++) {
                        if (combination % i == 0) {
                            isPrime = false;
                            break;
                        }
                    }
                    if (isPrime && combination != 0 && combination != 1)
                        answer++;
                }
                return answer;
            }
        }
//        String numbers = "17";
        String numbers = "011";
        Solution solution = new Solution();
        System.out.println(solution.solution(numbers));
    }
}