아찌방 하우스

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

풀이 - 나의 생각

순열을 사용해서 numbers로 만들 수 있는 모든 조합을 찾아가면서

Set에 저장(중복 제거를 위해)

그 후 소수의 갯수를 체크하면 된다.

코드

import java.util.*;
import java.util.stream.Collectors;

class Solution {
    static boolean[] visited;
    static String[] nums;
    static Set<Integer> set;
    
    public int solution(String numbers) {
        set = new HashSet<>();
        visited = new boolean[numbers.length()];
        nums = numbers.split("");
        makeNum(0, "");
        
        return set.stream()
                .filter(this::isPrime)
                .collect(Collectors.toList())
                .size();
    }
    
    public static void makeNum(int cnt, String stNum){
        if(!stNum.isEmpty()) {
            set.add(Integer.parseInt(stNum));
        }
        
        for(int i =0; i < nums.length; i++){
            if(visited[i]) continue;
            visited[i] = true;
            makeNum(cnt+1, stNum+nums[i]);
            visited[i] = false;
        }
    }
    
    public boolean isPrime(int num){
        if(num < 2) return false;
        for(int i = 2; i <= Math.sqrt(num); i++){
            if(num%i == 0) return false;
        }
        
        return true;
    }
}

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

풀이 - 나의 생각

소수는 1과 자기 자신으로만 나누어지는 수입니다.

이걸 판별하는 여러가지 방법이 있는데

저는 trial division(시도로 나누기) 방법을 사용했습니다.

 n이 주어질때

2부터 n의 제곱근까지만 확인하면 되는겁니다.

예를 들어서

16이 주어질 때

2분터 4(16의 제곱근)까지만 나누어 보면

소수인지 아닌지 판별이 가능한 것을 알 수 있습니다.

코드

class Solution {
    public int solution(int n) {
        int answer = 0;
        for(int i = 2; i <=n; i++){
            if(isPrimeNumber(i)) answer++;
        }
        return answer;
    }
    
    public static boolean isPrimeNumber(int num){
        if(num <= 1) return false;
        
        for(int i = 2; i <= Math.sqrt(num); i++){
            if(num%i == 0) return false;
        }
        
        return true;
    }
}