본 글은 글쓴이의 개인적인 생각이 담겨있을 수 있습니다.

프로그래머스 [Programmers]
LEVEL - 2
소수 만들기
https://programmers.co.kr/learn/courses/30/lessons/12977

🍀 문제 파악

문제

주어진 숫자 중 3개의 수를 더했을 때 소수가 되는 경우의 수를 구하려고 한다.
숫자들이 들어있는 배열 nums가 주어질 때,
nums에 있는 숫자들 중 서로 다른 3개를 골라 더했을 때
소수가 되는 경우의 갯수를 구하라.

주의사항

• nums에 들어있는 숫자의 수는 3개 이상 50개 이하이다.
• nums의 각 원소는 1 이상 1,000 이하의 자연수이다.
• nums의 원소는 서로 다릅니다.
• nums의 세 원소의 합은 다른 세 원소의 합과 값이 같더라도 다른 값으로 취급합니다.

🍁 해결

이번 문제의 핵심은 '에라토스테네스의 체'와 '네 번째 주의사항'이다.

먼저, 네 번째 주의사항은 프로그래머스에 정확하게 기재되어 있지 않은 부분인데,
질문을 보니 이 문제로 인하여 많은 어려움을 겪고 있는 분들이 많았다.
하지만 문제의 지문을 자세히 보면,
구하는 것이 소수의 갯수가 아니라 소수가 되는 경우의 수였기 때문에
충분히 그럴 수 있다고 생각한다.

다음은 '에라토스테네스의 체'인데 에라토스테네스의 체는
소수를 찾는 방법 중에 하나로 위키백과에서 알게 되었다.
위키백과에 잘 설명이 되어 있으니 모른다면 한 번 보는 것을 추천한다.

위키백과 - 에라토스테네스의 체
https://ko.wikipedia.org/wiki/%EC%97%90%EB%9D%BC%ED%86%A0%EC%8A%A4%ED%85%8C%EB%84%A4%EC%8A%A4%EC%9D%98_%EC%B2%B4

다음은 해결한 코드이다.

class Solution {
    public int solution(int[] nums) {
        boolean[] isPrime = new boolean[2998];
        for(int i = 2 ; i <= (1000 + 999 + 998) ; i++) {
            int sqrt = (int) Math.sqrt(i);
            isPrime[i] = true;
            for(int j = 2 ; j <= sqrt ; j++) {
                if(i % j == 0) {
                    isPrime[i] = false;
                    break;
                }
            }

            int n = i;
            while(isPrime[i]) {
                n *= 2;
                if(n >= isPrime.length)
                    break;
                isPrime[n] = false;
            }
        }

        int count = 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++) {
                    if(isPrime[nums[i] + nums[j] + nums[k]])
                        count++;
                }
            }
        }
        return count;
    }
}

코드는 첫 번째 for문과 두 번째 for문으로 구성되어 있는데,
첫 번째 for문은 에라토스테네스의 체를 구현하는 코드이고,
두 번째 for문은 에라토스테네스의 체를 이용하여 세 개의 수를 더해서 소수가 나오는
경우의 수를 구하는 코드이다.

🍂 느낀 점

이번 '소수 만들기' 문제를 해결하면서 문제의 지문을 정확하게 읽어야 한다는 것을 깨닫게 되었고,
"무식함에 꼼수를 더하라"라는 말을 이해하게 되었다.

프로그래머스의 지문이 일부로 속이려고 한 것은 아니겠지만,
지문의 의도를 잘 파악하면 충분히 알 수 있는 부분이었다.

또한 "무식함에 꼼수를 더하라"라는 말은 처음에는 '에라토스테네스의 체'라는 것을
생각하지 못하고 3중 for문을 이용하면 분명히 시간초과가 날 것이라고 생각해서
시도조차도 하지 못했다.

하지만 결과적으로는 3중 for문이라는 '무식함'에 에라토스테네스의 체라는 꼼수를 더해서
문제를 해결할 수 있었다.