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

코드 힌트:

1. 숫자의 모든 순열 생성:
   • 주어진 문자열의 각 숫자들로 만들 수 있는 모든 가능한 숫자의 순열을 구합니다. 이때, 숫자의 자릿수를 다양하게 설정하여 1자리, 2자리, ... 최대 n자리까지 모든 경우의 수를 고려합니다.
2. 소수 판별:
   • 각 순열로 만들어진 숫자가 소수인지 판별하고, 소수일 경우에만 HashSet에 저장합니다.
   • HashSet을 사용하는 이유는 중복된 소수를 배제하기 위해서입니다.
3. 순열과 소수 판별의 반복:
   • 순열 생성은 재귀적으로 처리하여, 아직 방문하지 않은 숫자를 추가하고, 방문 여부를 기록합니다.
   • 소수 여부를 확인할 때는 2부터 해당 숫자의 제곱근까지 나눠보는 방식으로 효율적으로 소수인지 확인합니다.

 

 

---

정답은 더보기 클릭

import java.util.*;

class Solution {
    
    static HashSet<Integer> primeNumbers = new HashSet<>(); // 소수를 저장할 HashSet
    
    public int solution(String numbers) {
        boolean[] visit = new boolean[numbers.length()]; // 숫자의 방문 여부를 체크하는 배열
        
        // 모든 가능한 숫자의 자릿수로 순열을 생성 (1자리, 2자리, ..., n자리)
        for (int i = 1; i <= visit.length; i++) {
            permutation(numbers, visit, 0, i, ""); // 순열 생성 시작
        }
        
        return primeNumbers.size(); // 저장된 소수의 개수를 반환
    }
    
    // 순열을 재귀적으로 생성
    public void permutation(String numbers, boolean[] visit, int idx, int count, String current) {
        if (idx == count) { // 원하는 자릿수에 도달한 경우
            int num = Integer.parseInt(current); // 현재 생성된 숫자로 변환
            
            // 소수 판별 후, 소수이면 HashSet에 추가
            if (num > 1 && isPrime(num)) {
                primeNumbers.add(num);
            }
        }
        
        // 각 자리의 숫자를 차례로 사용하여 순열을 생성
        for (int i = 0; i < visit.length; i++) {
            if (!visit[i]) { // 방문하지 않은 숫자를 선택
                visit[i] = true; // 해당 숫자 방문 표시
                permutation(numbers, visit, idx+1, count, current + numbers.charAt(i)); // 재귀 호출
                visit[i] = false; // 순열 생성을 마치면 방문 표시를 해제
            }
        }
    }
    
    // 소수 판별
    public boolean isPrime(int n) {
        boolean result = true;
        
        // 2부터 n의 제곱근까지 나누어 떨어지는지 확인
        for (int i = 2; i < (int) Math.sqrt(n) + 1; i++) {
            if (n % i == 0) {
                result = false; // 나누어 떨어지면 소수가 아님
                break;
            }
        }
        
        return result; // 소수 여부 반환
    }
}