[프로그래머스] 소수 만들기 (JAVA / 자바)

안녕하세요~ 코딩하는 코알못 코메인입니다.

 

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

코딩테스트 연습 - 소수 만들기

 

---

- 문제 -

 

풀이 방법

세수의 합을 구해서 2부터 일일히 나눠서 구해도 되지만 그렇게 되면 너무 많은 시간이 걸릴거라 예상이 되기에 에라토스의 체를 이용해 올 수 있는 값들의 소수 판별을 해두고, 세 수의 합이 판별해둔 소수에 해당하는지 확인하고, 개수를 리턴한다.

 

https://comain.tistory.com/253

[백준/BOJ] 1929번 : 소수 구하기 (JAVA / 자바)

에라토스테네스의 체에대한 간략한 설명은 위에 쓰여있다. 에라토스테네스의 체는 소수 판별 문제에서 아주 유용하게 쓰이기에 한번 확인하고 위 문제도 풀어보는 것을 추천한다.

 

코드를 보자.

---

-풀이-

 

class Solution {
    public int solution(int[] nums) {
        //중복된 숫자가 들어있지 않기때문에 정확히 올 수 있는 최대 값은
        //1000+999+998인 2997이기에 배열의 크기를 2998로 해줘도 된다.
        boolean[] arr = new boolean[3001];
        //0과 1은 소수가 아니다.
        arr[0] = arr[1] = true;
        
        //에라토스테네스의 체
        for(int i = 2; i * i <= 3000; i++){
            if(!arr[i]){
                for(int j = i * i; j <= 3000; j += i){
                    arr[j] = true;
                }
            }
        }
        
        //나올 수 있는 소수의 개수를 저장 할 변수
        int count = 0;
        //배열의 크기
        int size = nums.length;
        
        //세 값의 합을 구하는 3중 반복문
        for(int i = 0; i < size - 2; i++){
            for(int j = i + 1; j < size - 1; j++){
                for(int k = j + 1; k < size; k++){
                    if(!arr[nums[i] + nums[j] + nums[k]]) count++;
                }
            }
        }
        return count;
    }
}

---

-결과-

다른 사람들은 블로그에 풀이 후 다른 사람들이 좀 더 깔끔하게 한 풀이를 올려주는데 필자는 직접 풀기도 전에 풀이를 너무 많이 보는 것은 그 사람의 알고리즘 풀이 능력 향상에 큰 도움이 되지 않는다 생각한다. 정 안풀리면 보되 한가지만 보고 최대한 그걸 응용해서 자기가 다시 풀어보는 것을 추천한다. 다른 사람들꺼는 자신이 그 문제를 풀고 나서야 봐도 늦지 않는다고 생각한다.

---

아직 코딩 공부가 부족한 필자라 설명과 풀이 방법이 많이 미흡할 수 있다. 코딩 고수들은 보시고 문제점이 있다면 댓글로 말해주시면 감사한 마음으로 참고 수정 하겠다.