소수 찾기

• 문제 설명

  문제 설명

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

  각 종이 조각에 적힌 숫자가 적힌 문자열 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은 같은 숫자로 취급합니다.

• 문제 풀이

  • 순열을 사용하여 모든 조합 탐색

    참조 -> 순열

  import java.util.*;
    
  class Solution {
        
      static char[] ch;
      static boolean[] visited;
      static HashSet<Integer> set;
        
      public int solution(String numbers) {
          int answer = 0;
            
          int n = numbers.length();
          visited = new boolean[n];
          set = new HashSet();
            
          for (int i = 1; i <= n; i++) {
              ch = new char[i];
              perm(0, i, n, numbers);
          }
            
          answer = set.size();
            
          return answer;
      }
        
      public static void perm(int start, int r, int n, String numbers) {
          if (start == r) {
              if (ch[0] == '0') 
                  return;
              int num = Integer.parseInt(String.valueOf(ch));
                
              if (primeNumber(num)) {
                  set.add(num);
              }
              return;
          }
            
          for (int i = 0; i < n; i++) {
              if (visited[i]) 
                  continue;
              visited[i] = true;
              ch[start] = numbers.charAt(i);
              perm(start+1, r, n, numbers);
              visited[i] = false;
          }
      }
        
      public static boolean primeNumber(int num) {
          if (num == 1) 
              return false;
          for (int i = 2; i < num; i++) {
              if (num%i == 0) 
                  return false;
          }
          return true;
      }
  }