링크

문제링크

문제

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

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

제한사항

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

입출력

numbers	return
"17"	3
"011"	2

해결

Set 은 같은 조합의 수를 중복으로 저장하는것을 걸러내기 위해 사용하였다.

permutation() 은 numbers를 탐색하면서
visited에 방문하는 인덱스를 표시하고 재귀형식으로 더 깊은 탐색을 한다.
deepth가 targetLength 와 일치할때의 numStr을 set에 추가해 준다.

그리고 numberSet에 있는 숫자들을 checkPrimeNumber() 으로 소수인지 체크하여 소수의 갯수를 센다.

코드

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

class Solution {
    public int solution(String numbers) {
        int answer = 0;
        Set<Integer> numberSet = new HashSet<>();

        // 가능한 조합 찾기
        for (int i = 0; i < numbers.length(); i++) {
            permutation(numberSet, numbers, "", new boolean[numbers.length()], 0, i + 1);
        }

        // 소수 판별
        for (int number : numberSet) {
            if (checkPrimeNumber(number)) answer++;
        }
        
        return answer;
    }
    

    public static void permutation(Set<Integer> set, String numbers, String numStr, boolean[] visited, int deepth, int targetLength) {

        if (deepth == targetLength) {
            set.add(Integer.parseInt(numStr));
            return;
        }

        for (int i = 0; i < numbers.length(); i++) {
            if (!visited[i]) {
                visited[i] = true;
                String nextNumStr = numStr + numbers.charAt(i);
                permutation(set, numbers, nextNumStr, visited, deepth + 1, targetLength);
                visited[i] = false;
            }
        }
    }

    public static boolean checkPrimeNumber(int number) {
        if (number < 2) return false;

        for (int i = 2; i * i <= number; i++) {
            if (number % i == 0) return false;
        }

        return true;
    }
}