프로그래머스 완전탐색 Level 2 (소수 찾기)

문제

---

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

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

 

 

제한사항

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

 

 

 

풀이

---

두가지 알고리즘을 사용 하였다.

conpulake.tistory.com/72

순열, 조합, 부분집합, 멱집합 정리

여기서 정리한 순열 알고리즘과

conpulake.tistory.com/20?category=829591

백준 1978 ( 소수 찾기)

여기서 보여준 소수 찾기 알고리즘을 적절히 섞어서 사용하였다.

 

순열 알고리즘을 사용함에 앞서

흩어진 숫자카드가 n개라고 가정하면 1~n 개까지 선택하는 방법이 있다.

for(int i = 1 ; i <= numbers.length(); i++){
	reculsion(arr, result, numbers.length(), i);
}

이 와 같이 반복문을 통해 numbers의 갯수만큼 넣어줬다.

 

 

순열 코드는 아래와 같다.

public void reculsion(List<Character> arr, List<Character> result, int size, int r){
        
    if(r == 0){           
        String str = "";
        int length = result.size();
                
        for(int i = 0 ; i < length ; i++){
            str += result.get(i);
        }
                
        int num = Integer.parseInt(str);
            
        if(!set.contains(num)){
            set.add(num);
            
            if(isPrime(num)){
                System.out.println(num);
                answer++;             
            }
        }
        return;
    }
        
    for(int i = 0 ; i < size ; i++){
        result.add(arr.remove(i));
        reculsion(arr, result, size - 1, r - 1);
        arr.add(i, result.remove(result.size() - 1));
    }
}

 r = 0 이 된다는것은 선택하고자하는 숫자의 갯수를 모두 선택했다는 것이므로

그때까지 선택 된 수들이 소수인지를 판단하면 된다.

 

<전체코드>

import java.util.*;

class Solution {
    public int answer = 0;
    public HashSet<Integer> set = new HashSet<Integer>();
    
    public int solution(String numbers) {         
        
        List<Character> arr = new ArrayList<Character>();
        for(int i = 0 ; i < numbers.length(); i++){
            arr.add(numbers.charAt(i));
        }
        
        List<Character> result = new ArrayList<Character>();
        
        for(int i = 1 ; i <= numbers.length(); i++){
            reculsion(arr, result, numbers.length(), i);
        }
                
        return answer;
    }
    
    public boolean isPrime(int n){
        
        for(int i = 2 ; i * i <= n ; i++){
            if(n % i == 0)
                return false;
        }
        
        if(n > 1)
            return true;
        else
            return false;
    }
    
    
    public void reculsion(List<Character> arr, List<Character> result, int size, int r){
        
        if(r == 0){
            
            String str = "";
            int length = result.size();
                
            for(int i = 0 ; i < length ; i++){
                str += result.get(i);
            }
                
            int num = Integer.parseInt(str);
            
            if(!set.contains(num)){
                set.add(num);
                
                if(isPrime(num)){
                    System.out.println(num);
                    answer++;
                    
                }
            }
            return;
        }
        
        for(int i = 0 ; i < size ; i++){
            result.add(arr.remove(i));
            reculsion(arr, result, size - 1, r - 1);
            arr.add(i, result.remove(result.size() - 1));
        }
    }
}