Programmers - 완전탐색 [소수찾기]

1. 문제

문제 설명

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

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

제한사항

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

입출력 예

numbersreturn

17	3
011	2

입출력 예 설명

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

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

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

2. 내풀이

import com.sun.deploy.net.MessageHeader;

import java.util.*;


public class PrimeNumFinder {
    public static final HashSet<Integer> com = new HashSet<>();

    public int solution(String numbers) {
        int answer = 0;

        // 숫자를 int형으로 변환하여 배열에 저장
        int[] intNumbers = new int[numbers.length()];
        for (int i = 0; i < numbers.length(); i++) {
            // String 클래스에서 i번째 char값을 꺼내려면 charAt 메소드 사용해야한다.
            // 또한 char 값을 int형으로 변환하려면 char - '0' 해야한다.
            intNumbers[i] = numbers.charAt(i) - '0';
        }

        // 1개의 숫자만을 뽑는 방법부터 배열 전체를 뽑는 방법 까지 HashSet에 저장
        for (int i = 1; i <= intNumbers.length + 1; i++) {
            combination(intNumbers, i);
        }

        Iterator iter = com.iterator();    // Iterator 사용
        while (iter.hasNext()) {//값이 있으면 true 없으면 false
            System.out.println(iter.next());
            if (isPrimeNumber((Integer) iter.next())) answer++;
        }
        return answer;
    }


    public static void combination(int[] arr, int destNum) {
        int[] temp = new int[destNum];
        combination(arr, 0, destNum, temp);
    }

    // 원배열,
    public static void combination(int[] arr, int curLoc, int destNum, int[] temp) {
        // 결과물 출력부분
        if (0 == destNum) {
            String numStr = null;
            // temp는 숫자들을 모아놓은 배열이므로 그것자체를 String으로 만들고 int화 시키면된다.
            for (int i = 0; i < temp.length; i++) {
                numStr = Integer.toString(temp[i]);
                //System.out.println(numStr);
            }
            com.add(Integer.valueOf(numStr));
            return;
        }
        for (int i = curLoc; i < arr.length; i++) {
            temp[temp.length - destNum] = i;
            combination(arr, i + 1, destNum - 1, temp);
        }
    }

    public boolean isPrimeNumber(int number) {
        for (int i = 2; i < number; i++) {
            if (number % i == 0) return false;
        }
        return true;
    }

    public static void main(String[] args) {
        PrimeNumFinder primeNumFinder = new PrimeNumFinder();
        String numbers = "17";
        System.out.println(primeNumFinder.solution(numbers));
    }
}

- 못풀었다. 내가 생각한 풀이는 다음과 같다. 먼저 문자열을 int[] 배열에 조각 조각 담고 만들수 있는 조합을

만들어 문자열로 만들었다가 int형으로 만든다. 이후 HashSet에 집어 넣어 중복을 제거한다.

그리고 꺼내어 해당 숫자가 소수인지 판별한다. 판별하면 answer++ 해서 답을 낸다.

 

문제는 조합을 만드는 것이다. 도저히 조합을 만드는 방법을 모르겠다.

생각난 방법은 DFS였는데 노드도 없는 상황에서 모든 상황을 다 고려해야하니 어떤것을 해야할지 몰랐다.

3. 다른 사람 풀이

import java.util.HashSet;
class Solution {
    public int solution(String numbers) {
        HashSet<Integer> set = new HashSet<>();
        permutation("", numbers, set);
        int count = 0;
        // HashSet 사용하기
        // HashSet을 배열처럼 사용하기 위해서는 iterator()가 꼭 필요하다.
        // iterator().hasNext()는 다음 원소가 있는지 없는지 판별한다.
        while(set.iterator().hasNext()){
            // iterator().next()는 다음 원소를 불러온다.
            int a = set.iterator().next();
            set.remove(a);
            if(a==2) count++;
            if(a%2!=0 && isPrime(a)){
                count++;
            }
        }
        return count;
    }

    // 소수를 찾을 때는 0과 1을 상관없고 3부터 시작해서 짝수도 거른다음
    // 해당 숫자의 제곱근까지만 나눠서 0이면 소수가 아닌 것으로 판별한다.
    public boolean isPrime(int n){
        if(n==0 || n==1) return false;
        for(int i=3; i<=(int)Math.sqrt(n); i+=2){
            if(n%i==0) return false;
        }
        return true;
    }

    // 순열
    public void permutation(String prefix, String str, HashSet<Integer> set) {
        int n = str.length();
        //if (n == 0) System.out.println(prefix);
        if(!prefix.equals("")) set.add(Integer.valueOf(prefix));
        // 모든 글자들을 한글자 씩 빼서 prefix에 넣고 HashSet에 저장한다. 한 사이클 순열
        // 그 글자만 뺀 나머지 String만 재귀함수를 돌려서 결국에는 모든 글자에 대해 순열을 완성한다.
        for (int i = 0; i < n; i++)
            permutation(prefix + str.charAt(i), str.substring(0, i) + str.substring(i+1, n), set);
    }


}

모든 조합의 순열 Permutation - 재귀함수

- 모든 글자들을 prefix에 넣으며 소수를 판별해야되기 때문에 한글자 씩 넣으며 전체모든 조합의 순열을 검사하려면

각 글자를 뺀 것으로 가지를 그려나가면된다. 이 방법은 거르는 것이 없기때문에 어마어마한 수의 재귀 함수를 그려낸다.

- 17은 1이 prefix = "" 에 붙는경우 와 7이 붙는 경우로 나뉜다.

- prefix가 "1"인 경우에서 7이 붙을 경우와 아무것도 안붙는 경우로 나뉜다.  

- prefix가 "7"인 경우에서 1이 붙을 경우와 아무것도 안붙는 경우로 나뉜다.

 

즉, 1, 7, 17, 71 인경우가 나오는데 여기서 1을 제외하면 3개의 소수가 나온다.

재귀함수로 모든 조합의 순열이 나온다. 

 

소수판별

- 소수는 1과 자기자신외에 나누었을 때 0이 나오는 것이 없는 수 이다.

- 따라서 0과 1은 소수판별에 의미가 없고 3부터 해당숫자의 제곱근 까지만 판별하면 된다.

왜냐하면 제곱근을 초과하는 수는 해당수로 나눴을 때 나눠지지가 않기 때문이다.

- 짝수는 거르기 때문에 2씩 넘어간다.

4. Tip

- HashSet() 에서 iterator()사용 - hasNext(), -next() 블로그 정리

- permutation에서의 재귀함수 사용. 

- 재귀함수의 사용에 감을 잡도록 백준에서 연습해야겠다.