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

문제

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

프로그래머스

 

---

 

문제 개요

숫자가 적힌 종이 조각이 흩어져 있습니다. 이 조각들을 붙여서 소수를 만들 수 있는 숫자 조합이 몇 개인지 알아내는 문제입니다. 주어진 문자열 numbers로 만들 수 있는 모든 조합을 생성하여, 그 중 소수인 숫자를 찾아 개수를 반환하는 프로그램을 작성합니다.

문제 접근 방법

1. 모든 조합 생성: 주어진 문자열에서 한 자리 수부터 numbers.length 자리 수까지 가능한 모든 조합을 생성합니다.
2. 중복 제거: HashSet을 사용해 이미 확인된 숫자를 저장함으로써 중복 체크를 수행합니다.
3. 소수 판별: 생성된 숫자가 소수인지 확인하고, 소수일 경우 개수를 증가시킵니다.

 

import java.util.HashSet;

class Solution {
    private int answer = 0;
    private HashSet<Integer> seenNums = new HashSet<>();

    public int solution(String numbers) {
        String[] digits = numbers.split(""); 
        
        // 가능한 모든 길이의 조합을 찾기 위해 i를 1부터 numbers 길이까지 설정
        for (int i = 1; i <= numbers.length(); i++) {            
            permute(digits, new String[i], 0, new boolean[digits.length]);
        }
        
        return answer;
    }
    
    private void permute(String[] digits, String[] sel, int depth, boolean[] visited) {
        // 선택된 조합이 완성된 경우, 숫자로 변환하여 소수 여부 확인
        if (depth == sel.length) {
            int num = Integer.parseInt(String.join("", sel));
            if (!seenNums.contains(num)) {
                seenNums.add(num);
                if (isPrime(num)) {
                    answer++;
                }
            }
            return;
        }
        
        // 백트래킹을 통해 각 숫자를 선택하여 순열 생성
        for (int i = 0; i < digits.length; i++) {
            if (!visited[i]) {
                visited[i] = true;
                sel[depth] = digits[i];
                permute(digits, sel, depth + 1, visited);
                visited[i] = false;
            }
        }
    }
    
    // 소수 판별 함수
    private boolean isPrime(int num) {     
        if (num < 2) return false;      // 2보다 작은 숫자는 소수가 아님
        if (num == 2) return true;      // 2는 소수
        if (num % 2 == 0) return false; // 짝수는 소수가 아님
        
        // 소수 판별을 위한 반복문, 홀수로만 나눔
        for (int i = 3; i <= Math.sqrt(num); i += 2) {
            if (num % i == 0) return false;
        }
        return true;
    }
}