소수 찾기 (DFS)

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

프로그래머스

 

 

문제 풀이

 만들 수 있는 모든 숫자 조합을 찾아 정리한 뒤, 소수를 세어주면 된다. 사실 DFS를 응용해서 푸는게 가장 좋다. 

 

 

작성한 코드

import java.util.*;

class Solution {
    public int solution(String numbers) {
        Set<Integer> answer = new HashSet<>();

        String[] numbersArray =numbers.split("");

        int N = numbersArray.length;
        
        boolean[] visited = new boolean[N];
        Stack<String> includeNum = new Stack<>();

        for (int i = 0; i < N; i++) { // 모든 원소로 한 번씩 조합 시작
            if (numbersArray[i].equals("0")) continue; // 0으로 시작하지 않음
            dfs(numbersArray, i, visited, includeNum, answer);
            visited = new boolean[N];
        }

        return answer.size();
    }

    public static void dfs(String[] numbersArray, int i, boolean[] visited, Stack<String> includeNum, Set<Integer> answer) {

        includeNum.push(numbersArray[i]);
        visited[i] = true;

        for (int j = 0; j < numbersArray.length; j++) {

            if (i == j) continue; // 자신 Node와는 조합하지 않음
            if (visited[j]) continue; // 이미 방문한 Node는 방문하지 않음
            if (numbersArray.length == includeNum.size()) continue; // 가장 깊은 depth의 Node임.

            dfs(numbersArray, j, visited, includeNum, answer);
        }

        StringBuilder num = new StringBuilder();

        for (String inner : includeNum) {
            num.append(inner);
        }

        int result = Integer.parseInt(num.toString());
        
        if (isPrime(result))
            answer.add(result);
            
        includeNum.pop();
        visited[i] = false;
    }

    public static boolean isPrime(int num) {
        if (num == 2) return true;
        if (num == 1 || num % 2 == 0) return false;

        for (int i = 3; i <= Math.sqrt(num); i += 2) {
            if (num % i == 0) return false;
        }

        return true;
    }
}

 

 

참고: https://record47584.tistory.com/54

DFS (깊이 우선 탐색)