프로그래머스 lv2 소수 찾기

문제 링크

소수 찾기

풀이

import java.util.HashSet;

class Solution {
    
    HashSet<Integer> set = new HashSet<>();
    
    public int solution(String numbers) {
        int answer = 0;
        char[] chars = numbers.toCharArray();
        for (int i = chars.length; i > 0; i--) {
            permutation(chars, new char[chars.length], new boolean[chars.length], 0, i);
        }

        for (int num : set) {
            if (isPrimeNum(num)) {
                answer += 1;
            }
        }

        return answer;
    }

    // 소수 판단
    public boolean isPrimeNum(int num) {
        for (int i = 2; i < num; i++) {
            if (num % i == 0) return false;
        }
        return true;
    }

    // 순열
    public void permutation(char[] arr, char[] out, boolean[] visited, int depth, int r) {
        if (depth == r) {
            StringBuilder sb = new StringBuilder();
            for (char num : out) {
                sb.append(num);
            }

            if (sb.toString().trim().length() > 0 && Integer.parseInt(sb.toString().trim()) > 1) {
                set.add(Integer.parseInt(sb.toString().trim()));
            }
            
            return;
        }
        for (int i = 0; i < arr.length; i++) {
            if (!visited[i]) {
                visited[i] = true;
                out[depth] = arr[i];
                permutation(arr, out, visited, depth + 1, r);
                visited[i] = false;
            }
        }
    }
}

소감

• 순열도, 소수판단도 전부 내가 직접 코드를 짜지 못했다.
• 아무래도 dfs에 대해서 더 공부를 해야할 것 같다.(순열도..)