99클럽 코테 스터디 8일차 TIL, 완전탐색(소수 찾기)

1. 문제 정의

2. 문제 접근

dfs를 통해 만들어질 수 있는 숫자를 모두 구해 소수인지 판별해주면 될 것 같다.

3. 문제 풀이

1. dfs를 통해 만들어질 수 있는 경우의 수를 모두 구한다.
2. isPrim 함수를 통해 소수인지 판별한다.

4. 코드

import java.util.*;

class Solution {
    static List<Integer> list = new ArrayList<>();
    static boolean[] check = new boolean[7];
    
    public int solution(String numbers) {
     int answer = 0;

        for (int i = 0; i < numbers.length(); i++) {
            dfs(numbers, "", i + 1);
        }

        for (int i = 0; i < list.size(); i++) {
            if (isPrime(list.get(i))) answer++;
        }

        return answer;
    }
    static void dfs(String str, String temp, int l) {
        if (temp.length() == l) {
            int num = Integer.parseInt(temp);
            if (!list.contains(num)) list.add(num);
        } else {
            for (int i = 0; i < str.length(); i++) {
                if (!check[i]) {
                    check[i] = true;
                    temp += str.charAt(i);
                    dfs(str, temp, l);
                    check[i] = false;
                    temp = temp.substring(0, temp.length() - 1);
                }
            }
        }

    }

    static boolean isPrime(int n) {
        if (n < 2) return false;
        for (int i = 2; i*i <= n; i++) {
            if (n % i == 0) return false;
        }
        return true;

    }
}

5. 회고

처음에 dfs로 어떻게 모든 경우의 수를 구하는지가 어려웠다. 소수를 판별하는 알고리즘은 정형화 되있어 편했다. 완전탐색을 많이 연습해야겠다.