[프로그래머스/42839] 소수 찾기

30 Jan 2025 in Study / Coding Test

• ☑️ 문제
• ☑️ 풀이

☑️ 문제

프로그래머스 42839

☑️ 풀이

• dfs 를 이용하여 완전탐색을 해야하는 문제이다.
• 사실 dfs 를 어떻게 해야 하는 지 잘 기억이 안나서 다른 사람의 풀이를 보며 따라했다.
• 우선, 겹치는 숫자가 없게 하기 위해 HashSet 을 사용했고, dfs 메서드를 돌면서 나올 수 있는 모든 숫자를 찾아 HashSet 에 저장했다.
• 소수 판별은 예전에 에라토스테네스의 체를 이용한 걸 그대로 사용했다.
  • 자세한 건 아래 글을 참고하면 된다.

  [프로그래머스/135808] 소수 찾기

import java.util.*;

class Solution {
    static Set<Integer> set;
    boolean[] visited = new boolean[7];

    public int solution(String numbers) {
        int answer = 0;
        set = new HashSet<>();
        dfs(numbers, "", 0); 
        
        for (int num : set) {
            if (isPrime(num)) {
                answer++;
            }
        }
        
        return answer;
    }
    
    
    public void dfs(String numbers, String s, int depth) {
        if (depth > numbers.length()) {
            return;
        }
        
        for (int i = 0; i < numbers.length(); i++) {
            if (!visited[i]) {
                visited[i] = true;
                set.add(Integer.parseInt(s + numbers.charAt(i)));
                dfs(numbers, s + numbers.charAt(i), depth + 1);
                visited[i] = false;
            }
        }
    }
    
    public boolean isPrime(int num) {
        if (num < 2) {
            return false;
        }
        
        for (int i = 2; i <= Math.sqrt(num); i++) {
            if (num % i == 0) {
                return false;
            }
        }
        
        return true;
    }
}