5. 완전 탐색 - 소수 찾기

https://programmers.co.kr/learn/courses/30/lessons/42839?language=java
완전 탐색 - 소수 찾기

Solution class 변수 선언

String input ="" // 주어진 문자열을 저장할 변수
String tmp=""; // 조합을 임시로 저장할 변수
boolean [] is_used; // 문자들의 사용여부를 표시하는 배열
int combinations[]; // 지금까지 만들어진 조합들의 배열
int combinations_idx = 0 //지금까지 만들어진 조합들의 갯수를 저장할 변수
int count = 0; //조합중 소수가 있을 경우 추가되어 최종 반환할 변수

public int solution(String numbers) {
    //input에 입력받은 numbers 저장
    input = numbers;

    //numbers의 길이만큼의 is_used 배열 생성
    is_used = new boolean[input.length()];

    //만들어질 수 있는 최대
    combinations = new int[(int)Math.pow(numbers.length(),numbers.length())];
    Solution1(0);
    return count;
}

1. String input : 입력된 문자열을 저장할 공간
2. String tmp : 조합할 때 임시로 저장할 공간
3. boolean is_used [] : 문자열의 문자들이 사용됐는지 안됐는지 확인할 배열
4. int combinations [] : 지금까지 만들어진 조합들의 배열 ( 중복 조합을 제외하기 위해 )
5. int combinations_idx : 지금까지 만들어진 조합의 갯수를 알수 있다.
6. int count : 조합된 숫자가 소수일 경우 ++

Solution class 메서드 선언
1.void Solution1 ( int tmp_length )
문제 해결을 위한 메소드

void Solution1(int tmp_length){ //tmp_length는 지금까지 만들어진 조합의 길이를 뜻함
        //입력된 문자열과 tmp의 길이가 같으면 종료
        if(tmp_length == input.length())return;

        //input앞부터 차례차례 tmp에 저장
        for(int i=0;i<input.length();i++){

            //사용하고 있지 않은 문자일 경우
            if(!is_used[i]){
            	//다음 case를 위해 현재 tmp를 tmp_tmp에 저장
                String tmp_tmp = tmp;

                //tmp에 해당 문자 추가
                tmp += input.charAt(i); 

                //tmp가 그전에 조합되지 않은 조합일 시 해당 조건문 실행
                if(!exist(Integer.parseInt(tmp))){

                    //추가한 문자 사용함으로 전환
                    is_used[i] = true;

                    //combinations배열 마지막에 현재 tmp를 int로 변환하여 추가 (맨앞 0 제거)
                    combinations[combinations_idx++] = Integer.parseInt(tmp);

                    //추가한 조합이 소수일 경우 count++
                    if(Prime(Integer.parseInt(tmp)))count++;

                    //추가적으로 조합하기위해 조합된 문자열의 길이를 매개변수로 재귀
                    Solution1(tmp_length+1);
                }
                //다음 반복문을 위해 i번째 문자 사용안함으로 전환 tmp도 추가되기 전으로 다시 저장 
                is_used[i] = false;
                tmp = tmp_tmp;
            }
        }
    }

2.boolean exist(int tmp)
이미 조합된 조합일 경우는 true를 아닌 경우는 false를 반환해 주는 메서드

boolean exist(int tmp){
    //현재 만들어진 조합의 갯수와 같거나 작은 인덱스까지 비교
    for(int i=0;i<=combinations_idx;i++){

        //같은 조합이 있으면 true 반환
        if(combinations[i] == tmp)return true;

    }

    //없을 경우 false 반환
    return false;
}

3.boolean Prime(int num){ }
소수이면 true 소수가 아니면 false를 반환해 주는 메서드

boolean Prime(int num){
    //2보다 작을 경우 false 반환
    if(num < 2)return false;

    //2부터 매개변수로 넘어온 num의 제곱근까지의 숫자로 num을 나누어서 나누어질 경우 false 반환
    for(int i=2;i<=(int)Math.sqrt(num);i++){
        if( num % i == 0 )
            return false;
    }

    //모두다 해당 안된 경우 true 반환
    return true;
}