[완전 탐색/소수 판별] 소수 찾기 - Java

문제 바로가기

코딩테스트 연습 - 소수 찾기

완전 탐색으로 해당하는 숫자들을 만들고 얘들을 갖고 소수인지 판별하는 문제입니다.

import java.util.*;

class Solution {
    StringBuilder sb = new StringBuilder();
	Set<Integer> set = new HashSet<>();
	boolean[] isSelected;
	int answer = 0;
	
	public int solution(String numbers) {
        isSelected = new boolean[numbers.length()];
        
        // 조합으로 만들 수 있는 숫자 만들기
        for(int depth = 1; depth <= numbers.length(); depth++) {
        	dfs(numbers, depth);
        }
        
        for(int num : set) {
        	if(isPrime(num) == true) answer++;
        }
        
        return answer;
    }
	
	public void dfs(String numbers, int depth) {
		if(sb.length() == depth) {
            // 다 만들면 중복 제거를 위해 Set에 추가
			set.add(Integer.valueOf(sb.toString()));
			return;
		}
		
		for(int i = 0; i < numbers.length(); i++) {
			if(isSelected[i] == true) continue;
			isSelected[i] = true;
			sb.append(numbers.charAt(i));
			
			dfs(numbers, depth);
			
			sb.delete(sb.length()-1, sb.length());
			isSelected[i] = false;
		}
	}
	
	public boolean isPrime(int num) {
		if(num < 2) return false;
		for(int i = 2; i <= Math.sqrt(num); i++) {
			if(num % i == 0) return false;
		}
		
		return true;
	}
}

 

요번에는 에라토스테네스?? 의 체를 사용하지 않았습니다. 

DFS로 조합을 만듭니다. 오랜만에 만드네욤.

그리고 만들어준 애들은 Set에다가 넣읍시다. 별 이유 없습니다. 중복 제거를 위함입니다.

그리고 Set에 있는 친구들을 보면서 isPrime() 메소드에서 소수인지 판별해줍니다.

 

 

감사합니다!!!