[프로그래머스/Java] 완전탐색 > 소수 찾기

1. 문제

2. 접근 방식

주어진 문제 요약: 주어진 문자열에서 조합을 통해 만들 수 있는 소수의 개수 찾기

• 재귀함수 recursive 는 현재까지 만들어진 조합 comb 과 아직 사용하지 않은 나머지 숫자들 others를 파라미터로 받습니다.
  comb 가 비어있지 않으면(즉, 조합이 만들어져 있다면) 그 조합을 정수로 변환하여 numberSet에 추가합니다.
  그리고, others에 대해서 가능한 모든 조합을 만들기 위해 루프를 돌며 재귀적으로 recursive 함수를 호출합니다.

• isPrime 함수는 주어진 num이 소수인지 판별합니다.
  0 또는 1은 소수가 아니므로 false를 반환하여 제외시킵니다.
  그 이외의 경우, num의 제곱근까지의 숫자로 나누어보며 나누어떨어지는지 확인하여 소수 여부를 판별합니다.

• solution 함수 내부:
  (1) 조합을 저장할 HashSet을 선업합니다.
  (2) recursive("", numbers); : 초기에는 빈 문자열로 시작하여, numbers의 모든 조합을 생성합니다.
  (3) numberSet을 순회하기 위한 Iterator를 생성합니다.
  (4) numberSet의 모든 원소에 대해 반복문을 실행합니다.
  (5) 현재 순회 중인 값을 가져와서 소수인지 확인하고, 소수인 경우에 count를 증가시킵니다.
  (6) 더 이상 증가시킬 경우가 없다면, 최종적으로 찾은 소수의 개수가 담긴 count를 반환합니다.

3. 제출한 코드

import java.util.*;

class Solution {
    HashSet<Integer> numberSet = new HashSet<>();
    
    public int solution(String numbers) {
        
        int count = 0;
        
        recursive("", numbers);
        
        Iterator<Integer> it = numberSet.iterator();
        
        while(it.hasNext()) {
            int number = it.next();
            
            if (isPrime(number)) {
                count++;
            }
        }
        
        return count;
    }
    
    public boolean isPrime(int num) {
        if (num == 0 || num == 1) {
            return false;
        }
        
        int limit = (int) Math.sqrt(num);
        
        for (int i = 2; i <= limit; i++) {
            if (num % i == 0) {
                return false;
            }
        }
        
        return true;
    }
    
    public void recursive(String comb, String others) {
        if (!comb.equals("")) {
            numberSet.add(Integer.parseInt(comb));
        }
        
        for (int i = 0; i < others.length(); i++) {
            if (!comb.equals("")) {
                numberSet.add(Integer.valueOf(comb));
            }
            
            recursive(comb + others.charAt(i), others.substring(0, i) + others.substring(i + 1));
        }
    }
}