[프로그래머스 자바] 소수 만들기 (Lv. 1)

 

문제 

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

프로그래머스

 

 

 

풀이 

class Solution {
    
    int length = 1000 * 50;
    boolean[] composites = new boolean[length + 1];
    
    private void setPrimes() {
        composites[0] = composites[1] = true;
        
        for (int i = 2; i <= Math.sqrt(length); i++) {
            if (!composites[i]) {
                for (int j = i * i; j <= length; j += i) {
                    composites[j] = true;
                }
            }
        }
    }
    
    public int solution(int[] nums) {
        
        setPrimes();
        int answer = 0;
        
        for (int i = 0; i < nums.length - 2; i++) {
            for (int j = i + 1; j < nums.length - 1; j++) {
                for (int k = j + 1; k < nums.length; k++) {
                    int sum = nums[i] + nums[j] + nums[k];
                    if (!composites[sum]) {
                        answer++;
                    }
                }
            }
        }
        
        return answer;
    }
}

 

 

소수 나와서 에라토스테네스의 체를 이용해서 풀었다.

우선 nums 는 길이가 3이상 50이하 이고, 요소의 값범위는 1이상 1000이하이다. 

그래서 소수배열 길이를 50 * 1000 +1 로 정해두었다. 

 

보통 구글에서 에라토스테네스의 체를 이용하는 코드를 보면 isPrime 을 쓰곤 하는데, 나는 그게 직관적으로 이해가 잘 안 되어서 composites 로 해서, false면 소수가 되도록 했다. 

 

그래서 setPrimes()로 소수처리를 해둔 뒤에, 3중 포문으로 3개합을 구한 뒤 소수이면 카운팅하도록 했다. 

 

조금 오래 잡고 있었는데, 내가

if (!composites[sum]) {
    answer++;
}

 

이 부분을 

 

if (!composites[sum]) {
    answer++;
    composites[sum] = true;
}

이렇게 했더니 다른 조합의 같은 소수를 카운팅하지 않아서 자꾸 틀렸었다.