[JAVA] 완전 탐색 : 소수 찾기

1. 문제 내용

요약
입력된 문자열을 1개씩 분해하여 모든 조합에서 소수인 것을 찾기

2. 접근방법
 모든 경우의 수를 확인해야하므로 완전탐색 기법을 사용해봤다
그리고 중복되는 값의 경우는 Set을 사용해 제외하면 될 것 같다

3. 구현 과정

int count = 0;
char[] numberArray = numbers.toCharArray();
Queue<String> queue = new LinkedList<>();
Set<Integer> set = new HashSet<>();
for(char number : numberArray){
	queue.offer(String.valueOf(number));
}

입력된 값을 한글자씩 쪼개서 배열화하고 queue에 저장
queue는 값을 순차적으로 사용하기위해 사용
그리고 중복값을 제외하기위한 set

    public void search(Queue<String> queue, Set<Integer> set, String number){
        if(queue.isEmpty()) return;
        else{
            String temp = number;
            int length = queue.size();
            for(int i = 0; i < length; i++){
                String num = queue.poll();
                number += num;
                set.add(Integer.parseInt(number));
                search(queue, set, number);
                queue.offer(num);
                number = temp;
            }
        }
    }

경우의 수 탐색을 위한 메서드
queue가 빌 때까지 탐색하여 순차적으로 모든 조합을 set에 저장

public boolean isPrime(int num){
        if (num <= 1) {
            return false;
        }
        if (num == 2) {
            return true;
        }
        if (num % 2 == 0) {
            return false;
        }
        for (int i = 3; i * i <= num; i += 2) {
            if (num % i == 0) {
                return false;
            }
        }
        return true;
    }

소수 판별을 위한 메서드

for(Integer num : set){
            count += isPrime(num) ? 1 : 0;
        }

set에 저장된 값을 isPrime메서드를 이용해 소수일경우 1씩 더한다

4. 결과

전체코드

import java.util.HashSet;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Set;

class Solution {
    public int solution(String numbers) {
        int count = 0;
        char[] numberArray = numbers.toCharArray();
        Queue<String> queue = new LinkedList<>();
        Set<Integer> set = new HashSet<>();
        for(char number : numberArray){
            queue.offer(String.valueOf(number));
        }
        search(queue, set, "");

        for(Integer num : set){
            count += isPrime(num) ? 1 : 0;
        }

        return count;
    }

    public void search(Queue<String> queue, Set<Integer> set, String number){
        if(queue.isEmpty()) return;
        else{
            String temp = number;
            int length = queue.size();
            for(int i = 0; i < length; i++){
                String num = queue.poll();
                number += num;
                set.add(Integer.parseInt(number));
                search(queue, set, number);
                queue.offer(num);
                number = temp;
            }
        }
    }

    public boolean isPrime(int num){
        if (num <= 1) {
            return false;
        }
        if (num == 2) {
            return true;
        }
        if (num % 2 == 0) {
            return false;
        }
        for (int i = 3; i * i <= num; i += 2) {
            if (num % i == 0) {
                return false;
            }
        }
        return true;
    }
}