소수 찾기

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

프로그래머스

 

 

흩어진 종이 조각들을 모두 사용하지 않은 경우도 소수인지 판별을 해야한다.

 

처음엔 흩어진 종이조각으로 만들 수 있는 가장 큰 수를 기준으로 모든 소수를 구해놓고 진행했는데 이러니 타임아웃이 생겼다.

 

결국 조합되는 수 각각 소수 여부를 판별하되, 소수 판별에는 해당 수의 제곱근까지의 수만 나눠보는 식으로 진행.

 

import java.util.*;

class Solution {
    boolean[] visited;
    Map<Integer, Boolean> cache = new HashMap();
    int answer = 0;
    public int solution(String numbers) {
        
        String[] split = numbers.split("");
        
        visited = new boolean[split.length];
        
        for (int i = 0; i < split.length; i++) {
            visited[i] = true;
            check(split, i, "");
            visited[i] = false;
        }
        
        return answer;
    }
    
    void check(String[] numbers, int idx, String composition) {
        
        composition += numbers[idx];
        
        int num = Integer.parseInt(composition);
        
        if (!cache.containsKey(num)) {
            boolean isPrime = isPrime(num);
            if (isPrime) answer++;
            
            cache.put(num, isPrime);
        }
        
        if (composition.length() == numbers.length) return;
        
        for (int i = 0; i < numbers.length; i++) {
            
            if (visited[i]) continue;
            
            visited[i] = true;
            check(numbers, i, composition);
            visited[i] = false;
            
        }
        
    }
    
    boolean isPrime(int num) {
        
        if (num < 2) return false;

        for (int i = 2; i <= Math.sqrt(num) + 1; i++) {
            if (i != num && num % i == 0) return false;
        }
        
        return true;
    }
}