[Programmers] 소수 찾기

소수 찾기

풀이

• 입력으로 받은 스트링을 쪼개서 쪼갠 문자들로 만들 수 있는 소수의 개수를 새는 문제다.
• 스트링을 char 배열로 바꾸고, 이 배열에서 1,2,3,..배열길이 만큼 순열을 돌려서 만들어진 숫자가 소수인지 판별한 뒤, 중복이 되면 안되므로 Set 에 넣어주는 방식으로 풀었다.

  🙆‍♀️ 정답 풀이

  import java.util.*;
  class Solution {
      static int answer;
      static Set<Integer> decimalList = new HashSet<>();
      public int solution(String numbers) {
          answer = 0;
          char[] numberArr = numbers.toCharArray();
          char[] output = new char[numberArr.length];
          boolean[] visited = new boolean[numberArr.length];
          for(int i=0;i<numberArr.length;i++){
              permutation(numberArr,output,visited,0,i+1);
          }
          answer = decimalList.size();
          return answer;
      }
      private static void permutation(char[] arr, char[] res,boolean[] visited,int depth, int r){
          if(depth==r){
              StringBuilder sb = new StringBuilder();
              for(int i=0;i<r;i++){
                  sb.append(res[i]);
              }
              if(checkPrime(sb.toString())){
                  decimalList.add(Integer.parseInt(sb.toString()));
              }
          }
          for(int i=0;i<arr.length;i++){
              if(!visited[i]){
                  visited[i] = true;
                  res[depth] = arr[i];
                  permutation(arr,res,visited,depth+1,r);
                  visited[i] = false;
              }
          }
      }
      private static boolean checkPrime(String str){
          int checkNum = Integer.parseInt(str);
          if(checkNum<=1) return false;
          if(checkNum==2) return true;
          for(int i=2;i<checkNum;i++){
              if(checkNum%i==0) return false;
          }
          return true;
      }
  }