[프로그래머스] 소수 찾기 (완전탐색)

https://programmers.co.kr/learn/courses/30/lessons/42839?language=java 

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

2021-07-28

---

import java.util.*;
class Solution {
    public static String[] arr;
    public static boolean[] vtd;
    public static int answer;
    public static HashSet<Integer> set;
    static boolean prime(int num) {
        if(num == 0 || num == 1) return false;
        for(int i = 2; i <= Math.sqrt(num); i++) if(num % i == 0) return false;
        return true;
    }
    static void solve(String tmp, int cnt) {
        if(cnt == tmp.length()) {
            int num = Integer.parseInt(tmp);
            if(!set.contains(num)) {
                set.add(num);
                if(prime(num)) answer++;
            }
            return;
        }
 
        for(int i = 0; i < arr.length; i++) {
            if(!vtd[i]) {
                vtd[i] = true;
                solve(tmp + arr[i], cnt);
                solve(tmp + arr[i], cnt+1);
                vtd[i] = false;
            }
        }
    }
    static int solution(String numbers) {
        answer = 0;
        set = new HashSet<>();
        arr = new String[numbers.length()];
        vtd = new boolean[numbers.length()];
        for(int i = 0; i < numbers.length(); i++) arr[i] = String.valueOf(numbers.charAt(i));
 
        solve("", 1);
        
        return answer;
    }
 
}

#문제풀이 

사실 재귀에 좀 약한 편이다,,, 깔끔한 구현일지는 모르겠다.

 

hashset으로 중복을 걸렀고, 문자열 하나하나의 조합마다 prime 함수로 소수인지 아닌지 체크했다.