99클럽 코테 스터디 23일차 TIL : 완전탐색(프로그래머스 - 소수 찾기)

 

 

🔎 문제 

 

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

프로그래머스

 

 

---

💡 풀이

- DFS

- 같은 수 중복하지 않기 위해 Set<Integer> 자료구조 사용

- searchSosu() : 소수찾기

- isSosu(int num) : 해당 수(num)가 소수인지 판별(true - 소수/ false- 소수x) 

import java.util.*;

class Solution {
    public int solution(String numbers) {
        int answer = 0;
        char[] numArr = numbers.toCharArray();
        boolean[] visited = new boolean[numbers.length()];
        
        Set<Integer> ansSet = new HashSet<>();
        searchSosu(numArr, visited, ansSet, "");
        answer = ansSet.size();
        return answer;
    }
    
    private void searchSosu(char[] numArr, boolean[] visited, Set<Integer> count, String str) {
        if (!str.isEmpty()) {
            int num = Integer.parseInt(str);
            if (isSosu(num)) {
                count.add(num);
            }
        }
        
        for (int i = 0; i < numArr.length; i++) {
            if (!visited[i]) {
                visited[i] = true;
                searchSosu(numArr, visited, count, str + numArr[i]);
                visited[i] = false; // 원상 복구
            }
        }
    }
    
    public boolean isSosu(int num) {
        if (num < 2) return false;
        for (int i = 2; i <= Math.sqrt(num); i++) { // √num 까지만 확인
            if (num % i == 0) return false;
        }
        return true;
    }
}

 

 

📌 오늘의 회고

완전탐색에 점점 익숙해지고 있는 것 같다.

경우의 수가 적으면 전체를 탐색해도 시간이 많이 걸리지 않으니, 완전탐색 알고리즘을 사용한다.

 

방법은 여러가지가 있으니, 어떤 문제에 어떤 방법을 이용할지는 문제를 많이 풀어봐야 할것 같다.

 

* 완전탐색 알고리즘

① Brute Force 기법 - 반복 / 조건문을 활용해 모두 테스트하는 방법
② 순열(Permutation) - n개의 원소 중 r개의 원소를 중복 허용 없이 나열하는 방법
③ 재귀 호출
④ 비트마스크 - 2진수 표현 기법을 활용하는 방법
⑤ BFS, DFS를 활용하는 방법