[PGS] 소수 찾기 - JAVA

💡 문제

💬 입출력 예시

📌 풀이(소스코드)

import java.util.*;

class Solution {

    static ArrayList<Integer> list = new ArrayList<>();
    static boolean[] used = 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;
    }
    
    public void dfs(String numbers, String temp, int n) {
        if (temp.length() == n) {
            int num = Integer.parseInt(temp);
            if (!list.contains(num)) {
                list.add(num);
            }
        }
        
        for (int i = 0; i < numbers.length(); i++) {
            if (used[i]) continue;
            used[i] = true;
            temp += numbers.charAt(i);
            dfs(numbers, temp, n);
            used[i] = false;
            temp = temp.substring(0, temp.length() - 1);
        }
    }
    
    public 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;
    }
}

📄 해설

접근

• 주어진 숫자로 만들 수 있는 모든 숫자에 대해 소수 판정을 수행하면 되는 문제

과정

• 주어진 숫자 numbers 를 사용해서 만들 수 있는 모든 숫자를 찾고, 이를 list 에 추가한다.
• 이때의 과정은 DFS 를 수행해서 구현한다.
• 사용하지 않은 숫자면 임시 문자열 temp 에 추가하고 재귀 호출
• 재귀 수행 후에는 해당 숫자를 임시 문자열 temp 에서 제거
• 완료된 DFS 를 수행하여 얻은 숫자 리스트 list 를 순회하며 isPrime 메소드를 사용하여 소수 여부를 판별한다.
• 소수이면 answer 의 값을 증가시킨다.