[알고리즘과 자료구조] JAVA - 완전탐색 소수 찾기

문제 설명

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

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

제한사항

numbers는 길이 1 이상 7 이하인 문자열입니다.

numbers는 0~9까지 숫자만으로 이루어져 있습니다.

"013"은 0, 1, 3 숫자가 적힌 종이 조각이 흩어져있다는 의미입니다.

입출력 예 설명

예제 #1

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

예제 #2

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

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

문제풀이

import java.util.*;
class Solution {
    public int solution(String numbers) {
        int answer = 0;
        char[] numsCArr = numbers.toCharArray();
        
        // 경우의 수를 모두 담을 ArrayList
        ArrayList<Integer> numsArr = new ArrayList<>();
        
        for ( int i=1; i<=numsCArr.length; i++){
            // 재귀함수 호출
            permutation(numsCArr, numsArr, 0, i);
        }
        
        // numsArr 리스트에 추가된 배열 값에서 소수를 찾는다.
        for( int i=0; i<numsArr.size(); i++ ){
            // 소수이면 answer++
            if (!decimal(numsArr.get(i))){
                answer++;
            }
        }
        
        return answer;
    }
    
    // 순열 재귀함수
    public void permutation(char[] numsCArr, ArrayList<Integer> numsArr, int depth, int length){
        
        // depth와 length가 같으면 list에 값을 추가.
        if( depth == length ){
            StringBuffer sb = new StringBuffer();
            for ( int i=0; i<length; i++){
                sb.append( numsCArr[i] );
            }
            
            if( !numsArr.contains(Integer.parseInt( sb.toString())) && Integer.parseInt( sb.toString()) > 1 ){
                numsArr.add( Integer.parseInt( sb.toString() ));
            }
            
            return;
        }
        
        for ( int i=depth; i<numsCArr.length; i++){
            // testcase "17"의 경우 0번째, 0번째를 스왑해서 17 그대로 삽입
            // 다음은 0, 1을 스왑 "71" 삽입
            swap(numsCArr, i, depth);
            permutation(numsCArr, numsArr, depth+1, length);
            
            // 다시 swap 해서 배열 index를 제위치로
            swap(numsCArr, i, depth);
        }
    }
    
    // 순열 재쉬함수에서 swap
    public void swap (char[] numsCArr, int i, int j){
        char tmp = numsCArr[i];
        numsCArr[i] = numsCArr[j];
        numsCArr[j] = tmp;
    }
    
    // 소수 찾기
    public boolean decimal(int num) {
        boolean decimal = false;
        for ( int i=2; i<num; i++ ){
            // i로 나눈 나머지가 0이면 소수가 아니다.
            if( num % i == 0 ){
                decimal = true;
                break;
            }
        }
        return decimal;
    }
}