[프로그래머스] 소수찾기(완전탐색, 소수 찾기)

문제

프로그래머스

 

 

사고 과정

• 완전 탐색으로 숫자 조합 배열에 저장하기
• 배열 하나씩 돌면서 소수 찾기

 

코드

import java.util.HashSet;

public class Solution {
    HashSet<Integer> numberSet = new HashSet<>();
    
    public int solution(String numbers) {
        permutation("", numbers); // 가능한 모든 숫자 조합 생성
        return (int) numberSet.stream().filter(this::isPrime).count(); // 소수의 개수를 반환
    }
    
    void permutation(String prefix, String str) {
        int n = str.length();
        if (!prefix.isEmpty()) numberSet.add(Integer.valueOf(prefix)); // 숫자 조합을 HashSet에 추가
        for (int i = 0; i < n; i++)
            permutation(prefix + str.charAt(i), str.substring(0, i) + str.substring(i+1, n));
    }
    
    boolean isPrime(int number) {
        if (number <= 1) return false; // 1 이하의 경우 소수가 아님
        for (int i = 2; i*i <= number; i++) { // 제곱근까지만 확인
            if (number % i == 0) return false; // 나누어떨어지면 소수가 아님
        }
        return true; // 소수임
    }
}

• HashSet = 중복제거
• 소수 찾는 법
• 완전탐색 로직 익숙