프로그래머스 - 소수찾기

해당 알고리즘 자료는 제가 직접 푼 것도 있지만 다른 분들의 풀이과의 비교를 통해 더 나은 알고리즘을 공부하기 위해 정리한 것들입니다.

프로그래머스 - 소수찾기

https://programmers.co.kr/learn/courses/30/lessons/42839

풀이 : Set을 이용하여 중복을 제거하고 완전탐색을 통해 해당되는 소수를 찾는다.

import java.util.*;
class Solution {
    public int solution(String numbers) {
        HashSet <Integer> set = new HashSet<Integer>();
		calc("", numbers, set);
		int cnt = 0;
		for(int i : set) {
			if(isTure(i) || i == 2) cnt++;
		}
		return cnt;
	}

	private static boolean isTure(int i) {
		if(i <= 1) return false;
		if(i % 2 == 0) return false;
		for (int j = 3; j <= Math.sqrt(i); j++) {
			if(i % j == 0) return false;
		}
		return true;
	}

	private static void calc(String pre, String numbers, HashSet<Integer> set) {
		if(!pre.equals("")) {
			set.add(Integer.valueOf(pre));
		}
		
		for (int i = 0; i < numbers.length(); i++) {
			calc(pre + numbers.charAt(i), numbers.substring(0, i) + numbers.substring(i+1), set);
		}
	}

}