Programmers 완전탐색 소수찾기 java 풀이

풀이와 문제는 아래에

 

코드

import java.util.*;

class Solution {
    public int solution(String numbers) {
        int answer = 0;
        String[] tempArr = numbers.split("");
        int[] arr = new int[tempArr.length];
        for(int i=0; i<arr.length; i++) {
            arr[i] = Integer.parseInt(tempArr[i]);
        }
        
        Set<Integer> set = new HashSet<>();
        for(int i=1; i<=arr.length; i++) {
            perm(tempArr, 0, i, set);
        }
        answer = set.size();
        return  answer;
    }
    
    public void perm(String[] arr, int depth, int k, Set set) {
        //depth는 재귀함수 깊이, k는 만들어 낼 숫자의 길이
        if(depth==k) {  //숫자의 길이만큼 재귀 반복했는지
            StringBuilder sb = new StringBuilder();
            for(int i=0; i<k; i++) {
                sb.append(arr[i]);
            }
            isPrime(set, sb.toString());
            return;
        } else {
            for(int i=depth; i<arr.length; i++) {
                swap(arr, i, depth);
                perm(arr,depth+1,k,set);
                swap(arr,i,depth);
            }
        }
    }
    
    public void swap(String[] arr, int idx1 , int idx2) {
        String temp = arr[idx1];
        arr[idx1] = arr[idx2];
        arr[idx2] = temp;
    }
    
    public void isPrime(Set set, String str) {
        int num = Integer.parseInt(str);
        
        if(num<=1 || (num!=2 && num%2==0)) return;
        boolean flag = true;
        for(int i=3; i<=(int)Math.sqrt(num); i+=2) {
           if(num%i==0) {
                flag = false;
                break;
            }
        }
        if(flag) {
            set.add(num);
        }
    }
    
}

 

문제 풀이

 

 문제를 처음 접할 땐 소수찾기와 재귀함수로 구성되겠구나 금방 생각 할 수 있었는데, 소수찾기 알고리즘은 이미 여러 방법으로 몇번이나 구현해 보았기 때문에 수월했다. 문제는 주어지는 숫자를 조합해서 모든 경우의 수를 찾아내는 것이었다. 이를 순열 알고리즘 이라고 부르고 이를 구현하기 위해선 재귀함수의 이해가 필수적이었다. 결과적으론 순열 함수 알고리즘은 따로 학습해서 이번 문제풀이에 적용해야 했기에 시간이 오래걸렸다... 중복값 제거는 단순하게 set에 넣어만 주면 되기 때문에 쉽게 해결할 수 잇었다.

 

 

문제 설명

 

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

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

 

제한사항

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