★[200918] 소수 찾기 - 완전탐색(level2)

**주목해야 할 문제 : 완전탐색의 대표적인 예인 "순열, 조합"을 이용한 문제

1. 문제 이해

- numbers : 한자리 숫자가 적힌 종이 조각(1~7의 길이인 문자열)

- numbers의 종이 조각들을 조합하여 만들 수 있는 소수의 개수 return

 

 

2. 전략

(1) 종이조각 나누기 : substring을 이용해 String 배열에 넣기

 

(2) 대상이 되는 경우들 구하기(완전 탐색)

- 순열을 이용해 모든 경우를 담은 HashSet 만들기

- 순열 : 자리 고정 & swap 방식 이용

esw-csmoon.tistory.com/entry/%EC%88%9C%EC%97%B4%EC%A1%B0%ED%95%A9-%EC%99%84%EC%A0%84%ED%83%90%EC%83%89

순열/조합 (완전탐색)

(3) 소수인 것만 골라내기(조건 적용)

: 에라토스테네스 체 이용

- HashSet의 max값 고르기

- 2 ~ Math.sqrt(max)의 범위 내 배수에 해당하면 check를 true로 변경

 

 

3. 참고사항

(1) 다른 풀이 - 순열 루틴의 개선 : 모든 k값에 대해 구하기 때문에 이용할 수 있는 방법

- for문 + substring으로 차례로 요소 선택

- 재귀함수 돌 때마다 HashSet에 add

public void permutation(String prefix, String str, HashSet<Integer> set) {
        int n = str.length();
        if(!prefix.equals("")) set.add(Integer.valueOf(prefix));
        for (int i = 0; i < n; i++)
          permutation(prefix + str.charAt(i), str.substring(0, i) + str.substring(i+1, n), set);
}

(2) 다른 풀이 - 소수 구하기 : HashSet의 각 수마다 홀수로 나눠보기도 가능

(But 시간 오히려 더 걸릴 듯)

 

 

4. 코드

import java.util.*;

class Solution {
    HashSet<Integer> result = new HashSet<>();
    public int solution(String numbers) {
        int answer = 0;
        //1. 종이조각 나누기
        String[] arr = new String[numbers.length()];
        for(int i = 0; i < numbers.length(); i++){
            arr[i] = numbers.substring(i, i+1);
        }
        
        for(int i = 1; i <= numbers.length(); i++){ //2. 순열
            perm(arr, 0, arr.length, i, result);
        }
        //3. 소수찾기(에라토스테네스의 체)
        int max = 0;
        Iterator<Integer> itr = result.iterator();
        while(itr.hasNext()){
            int target = itr.next();
            if(target > max) max = target;
        }
        boolean[] check = new boolean[max+1];
        check[0] = true; check[1] = true;
        for(int i = 2; i <= Math.sqrt(max); i++){
            if(!check[i]){
                for(int j = 2; j*i <= max; j++){
                    check[j*i] = true;
                }
            }
        }
        itr = result.iterator();
        while(itr.hasNext()){
            int target = itr.next();
            if(!check[target]) answer++;
        }
        return answer;
    }
    
    public void perm(String[] arr, int depth, int n, int k,HashSet<Integer> result){ //순열함수 - n개 중 k개 나열
        if(depth == k){
            String base = "";
            for(int i = 0; i < k; i++){
                base = base + arr[i];
            }
            result.add(Integer.parseInt(base));
        }
        for(int i = depth; i < n; i++){
            swap(arr, depth, i);
            perm(arr, depth+1, n, k, result);
            swap(arr, depth, i);
        }
    }   
    public void swap(String list[], int a, int b){
        String temp = list[a];
        list[a] = list[b];
        list[b] = temp;
    }
}