Programmers - 소수 만들기 with JAVA

 

문제

nums라는 배열에서 서로 다른 인덱스의 위치한 3개의 수를 골라 소수를 만들 때, 만들 수 있는 소수의 개수를 구하라.

 

 

 

해결

이 문제는 굉장히 간단하나 소수를 구할 때, 에라토스테네스 공식을 쓰면 아주 시간 복잡도가 개선됨을 깨달았고 Boolean[] 이 아닌 boolean[] 처리시 초기값이 모두 false 처리 됨을 몰랐던 나의 무지함을 기록하기 위해 작성한다.

 

에라토스테네스의 공식은 간단하게 2부터 시작하여 해당 수를 곱한 모든 수는 소수이다.

예를 들어, 2*2, 2*3, 2*4 ... 3*3, 3*4.... 모두 소수이다 따라서 소수를 미리 체크하고 모든 수 하나하나를 소수 체크할 필요없이 미리 처리해놓는 방식이다. 문제에서 3가지 수로 만들수 있는 가장 큰수가 3000이므로 범위를 아래와 곱하기 값이 3000이하이게 설정한다.

 

 

 

코드

import java.util.*;
class Solution {
    private boolean[] prime = new boolean[3001];
    public int solution(int[] nums) {
        int result = 0;
        int length = nums.length;
        setPrimeArr();
        for(int i=0; i<length; i++){
            for(int j=i+1; j<length; j++){
                for(int k=j+1; k<length; k++){
                    int value = nums[i] + nums[j] + nums[k];
                    if(!prime[value]){
                        result += 1;
                    }
                }
            }
        }
        return result;
    }
    private void setPrimeArr() {
        for(int i=2; i*i <= 3000; i++)
            for(int j=i; i*j <= 3000; j++)
                prime[i*j] = true;
    }
}

 

 

import java.util.*;
class Solution {
    public static int answer = 0;
    public int solution(int[] nums) {
        find(nums, new boolean[nums.length], 0, 0, 0);
        return answer;
    }
    public static void find(int[] nums, boolean[] visited, 
                            int start, int result, int count){
        if(count == 3){
            check(result);
            return;
        }
        for(int i=start; i<nums.length; i++){
            if(!visited[i]){
                visited[i] = true;
                result += nums[i];
                find(nums, visited, i+1, result, count+1);
                result -= nums[i];
                visited[i] = false;
            }
        }
    }
    public static void check(int result){
        boolean value = true;
        for(int i=2; i<=(int)Math.sqrt(result); i++){
            if(result % i == 0){
                value = false;
                break;
            }
        }
        if(value){
            answer += 1;
        }
    }
}