[JAVA] 소수 찾기 (코딩테스트 고득점 Kit [ 완전탐색 ]) - LEVEL2

📂문제 설명

 

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

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

제한사항

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

입출력 예

numbersreturn

17	3
011	2

입출력 예 설명

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

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

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

---

📂아이디어 및 알고리즘(문제 풀이)

• 먼저 조합으로 풀지 혹은 순열로 풀지 고민해야 한다. 나는 여기서 조합을 먼저 생각했지만 너무 복잡해질거 같아서 순열을 이용하여 풀도록 하였다.
• String numbers를 char[]배열로 바꿔주어서 넣어주어 순회를 하기 쉽게 만들었다. 이 문제는 순열과 소수 찾기를 필요로 하기 때문에
• 순열을 만드는 perm 함수와 소수를 찾는 PrimeNum 함수를 만들었다.
• 순열 함수 Perm( char[] arr , int depth, int k, Set sosu )
  • depth와 k를 이용하여 현재 몇개의 수를 뽑아 냈는지를 계속 확인해준다.
  • 재귀함수로 매번 순회하면서 i, depth의 arr[index]값을 계속해서 바꿔준다. [ 순열 순서를 매번 바꿔준다. ]
  • 1번째 swap에서는 순열을 바꿔줌으로서 depth를 순회하고 
  • 2번째 swap에서는 바뀌었던 순열들을 다시 원래대로 돌리는 과정이다.
  • depth == k 가 되는 순간 make_num()을 통해 char[]을 String으로 만들어준다.
  • [ 맨 밑에 순열 로직에 대한 링크를 달아두었다 ]
• 소수 PrimeNum(int n)
  • n을 기준으로 2부터 n까지의 소수를 찾아내는 함수이다. 
  • 여기서 사용한 방법은 "에라토스테네스의 체"로 소수를 판별했다.
  • Boolean PrimeArr[] 로 소수가 아닌 수는 true로 하여 구분하였고
  • Judge_Prime()함수에서 해당 수에 값이 false이면 소수이므로 HashSet에 저장하도록 하였다. 

 

📂소스 코드

import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashSet;
import java.util.Set;
class Solution {
   static boolean[] PrimeArr = new boolean[10000000]; 
    
    public int solution(String numbers) {        
        char[] numbers_char = numbers.toCharArray();
        PrimeNum(10000000);
        
        //소수 구하기 (중복제외)
        Set<Integer> sosulist = new HashSet<Integer>();
        
        //i는 수열의 자릿수를 의미한다.
        for(int i=1;i<=numbers_char.length;i++) {
            perm(numbers_char,0,i,sosulist);
        }
        return sosulist.size();
    }
    
    // depth는 현재 몇개 뽑아냈는지, k는 몇개를 뽑아내서 순열을 만들것인지
    public static void perm(char[] arr, int depth, int k, Set sosu) {
        if(depth == k) {            
            make_num(arr,k,sosu);
            return;
        }
        for(int i=depth;i<arr.length;i++) {
            swap(arr, i, depth);
            perm(arr, depth+1, k, sosu);
            swap(arr, i, depth);
            
        }
    }
    
    //char배열을 String으로
    public static void make_num(char[] arr, int k, Set sosu) {
        StringBuilder str = new StringBuilder();
        for(int i=0;i<k;i++) {
            str.append(arr[i]);
        }
        JudgePrime(sosu, str);        
    }
    
    //소수 찾기
    public static void PrimeNum(int n) {
        //소수가 아니면 전부 true
        PrimeArr[0] = PrimeArr[1] = true;
        
        for(int i= 2; i*i<n ;i++) {
            if(!PrimeArr[i]) {
                for(int j = i*i;j<n;j +=i) PrimeArr[j] = true;
            }
        }        
    }
    
    //소수 판단
    public static void JudgePrime(Set sosu, StringBuilder str) {
        int num = Integer.parseInt(String.valueOf(str));
        if(!PrimeArr[num]) sosu.add(num);
    }
    
    public static void swap(char[] arr, int x, int y) {
        char temp = arr[x];
        arr[x] = arr[y];
        arr[y] = temp;
    }
    
}

📂코드 결과

 

📂후일담

간단한 문제인줄 알았는데 나에게 너무 힘든 시련을 주었던 문제이다.💨 조합으로 풀려 했던 난 많은 시간을 버리고 난 후에야 순열로 해야하나? 싶었고 처음에 바로 로직이 생각나지 않아서 고뇌한 시간이 많았다. 그러다 밑에 하단에 링크를 통해 다시 공부했고 풀 수 있었다.  [ 노력하도록 하자...  ]

이번 기회에 순열에 관한 트리를 다시 공부 할 수 있어서 좋았다🔥🔥🔥

 

 

 

 

[ JAVA_순열 로직 링크 ]  https://gorakgarak.tistory.com/522