코딩테스트 고득점 kit / 완전탐색 / 소수 찾기

 

나의 풀이

import java.util.Set;
import java.util.HashSet;

class Solution {

    public void permutation(int[] arr, int start, int end, Set set){
       
        if(start == end){
   
            StringBuilder sb = new StringBuilder();
            for(int i=0; i<start; i++){
                sb.append(arr[i]);
            }
            
            int n = Integer.parseInt(String.valueOf(sb));
            boolean b = true;
            
            if(n < 2) return;
            for(int i=2; i*i<=n; i++){
                if(n % i == 0) {
                    b = false;
                    break;
                }
            }
            
            if(b) set.add(n);
            return;
        } 
        
        for(int i=start; i<arr.length; i++){
            swap(arr, start, i);
            permutation(arr, start + 1, end, set);
            swap(arr, start, i);
        }
        
    }
    
    public void swap(int[] arr, int i, int j){
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }
    
    public int solution(String numbers) {
        int answer = 0;
        
        int[] arr = new int[numbers.length()];
        for(int i=0; i<numbers.length(); i++){
            arr[i] = Character.getNumericValue(numbers.charAt(i));
        }
        
        Set set = new HashSet();
        for(int i=1; i<=arr.length; i++){
            permutation(arr,0,i,set);
        }
        
        answer = set.size();
        return answer;
    }
}

이 문제는 순열을 활용하는 문제입니다.

처음에는 이 문제를 보고 다양한 풀이법을 생각하실 수 있습니다.

 

그러나 이중for문을 이용하여 substring을 이용해서 숫자들이 나올 수 있는 경우의 수를 구하려고 하면 "011" 로 "101"을 만들 수 없는 경우가 생깁니다.

 

그리고 Hash문제 풀때처럼 Map의 getOrDefault()메소드를 이용해서 숫자마다 개수를 Map에 저장하는 방법을 생각하면

그것을 이용해서 경우의 수 가짓수를 구하는 것 까지는 가능해도 가능한 문자열을 만드는 방법이 불가능해집니다.

 

따라서 순열을 이용해야 합니다.

즉, 모든 수를 나올 수 있는 경우의 수로 계산하려면 재귀함수를 이용한 순열을 사용하여야 합니다.

순열에 대한 풀이 방법은 아래링크의 개발자분 코드를 보고 참조하여 만들어봤습니다.

프로그래머스 알고리즘 : 소수 찾기 (java)

다른 분들 풀이보니까 순열을 이용할때 swap 대신 substring을 사용하여 숫자를 교환하시는 분들도 있는데 나중에 한번 참고해서 공부해야겠습니다.

 

 

히스토리

chucoding/algorithm