자바(JAVA) - 소수 찾기(Programmers : 42839)

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

코딩테스트 연습 - 소수 찾기

재귀를 이용한 완전탐색으로 풀 수 있었던 문제.
문제를 보자마자 재귀를 통해 완전탐색을 구현해야 함은 알았으나,,
중복 문자를 제거해가며 모든 조합을 어떻게 효율적으로 만들 수 있을지 생각해보다가 substring을 사용.
소수 검증 로직은 몇몇가지 조건으로 예외 처리 후, 제곱근 값까지만 확인.
앞에 0이 붙은 문자열의 경우 int로 parsing 시, 기존에 확인한 정수와 동일한 수 있어,
중복된 값은 무시할 수 있게 D.T. 는 HashSet으로 사용

 

실행 순서는 다음과 같다 :

    1. Input 문자열을 쪼개 모든 조합을 만들 수 있는 재귀함수 구현

    2. 소수인지 검증하는 메소드 구현

    3. 소수일 경우는 HashSet에 추가

    4. HashSet 크기 반환

 

 

<코드>

import java.util.*;
class Solution {
    HashSet<Integer> set;
    public int solution(String numbers) {
        set = new HashSet<Integer>();
        int answer = 0;
        
        recurStrBuilder(numbers, "");
        
        answer = set.size();
        return answer;
    }

    // 전체 String 조합을 만드는 재귀 메소드
    public void recurStrBuilder(String input, String prefix) {
        
        // 소수일 경우 Set에 추가
        if(!prefix.equals("")) {
            checkPrime(prefix);
        }
        int len = input.length();
        
        // prefix에 charAt(i)으로 반환된 문자가 더해진 문자열 +
        // input에서 반환된 문자가 빠진 문자열을 Args로 재귀 반복
        for(int i = 0; i < len; i++) {
            recurStrBuilder(input.substring(0, i) + input.substring(i + 1, len), prefix + input.charAt(i));
        }
    }
    
    // 소수 확인 메소드
    public void checkPrime(String num) {
        
        int numInt = Integer.parseInt(num);
        int maxToCheck = (int)Math.sqrt(numInt);
        
        // 2에 대한 예외처리 
        if(numInt == 2) {
            set.add(numInt);
            return;
        }
        
        // 2보다 작은 정수, 그리고 짝수에 대한 예외처리 
        if(numInt < 2 || numInt % 2 == 0) {
            return;
        }
        
        // 제곱근값까지만 확인하여 소수 확인
        for(int i = 3; i <= maxToCheck; i++) {
            if(numInt % i == 0) 
                return;
        }
        set.add(numInt);
    }
}