소수 만들기 - 12977

문제 설명
주어진 숫자 중 3개의 수를 더했을 때 소수가 되는 경우의 개수를 구하려고 합니다. 숫자들이 들어있는 배열 nums가 매개변수로 주어질 때, nums에 있는 숫자들 중 서로 다른 3개를 골라 더했을 때 소수가 되는 경우의 개수를 return 하도록 solution 함수를 완성해주세요.

제한사항
nums에 들어있는 숫자의 개수는 3개 이상 50개 이하입니다.
nums의 각 원소는 1 이상 1,000 이하의 자연수이며, 중복된 숫자가 들어있지 않습니다.

입출력 예
nums result
[1,2,3,4] 1
[1,2,7,6,4] 4

입출력 예 설명
입출력 예 #1
[1,2,4]를 이용해서 7을 만들 수 있습니다.

입출력 예 #2
[1,2,4]를 이용해서 7을 만들 수 있습니다.
[1,4,6]을 이용해서 11을 만들 수 있습니다.
[2,4,7]을 이용해서 13을 만들 수 있습니다.
[4,6,7]을 이용해서 17을 만들 수 있습니다.

---

설계

입력값의 조합을 만들고 그 조합의 합이 소수라면 Count를 1씩올려 return 하게 만든다.

 

구현

#include <vector>
#include <iostream>
using namespace std;

bool PrimeNum(int num)
{
    int count = 0;

    for (int i = 1; i <= num; i++)
    {
        if (num % i == 0)
        {
            count++;
        }
    }

    if (count == 2)
    {
        return true;
    }

    return false;
}


int solution(vector<int> nums) {
    int answer = 0;
    int total = 0;
    if (nums.size() == 3)
    {
        total = nums[0] + nums[1] + nums[2];
        if (PrimeNum(total))
        {
            answer++;
        }
    }
    else
    {
        for (int i = 0; i < nums.size() - 2; i++)
        {
            for (int j = i+1; j < nums.size() - 1; j++)
            {
                for (int k = j+1; k < nums.size(); k++)
                {
                    total = nums[i] + nums[j] + nums[k];

                    if (PrimeNum(total))
                    {
                        answer++;
                    }
                }
            }
        }
    }

    return answer;
}

---

리펙토링

#include <vector>
#include <iostream>

using namespace std;

// 숫자가 소수인지 판별하는 함수 (최적화 버전)
// true를 반환하면 소수, false를 반환하면 소수가 아님
bool isPrime(int num) {
    // 1. 예외 처리: 1 이하의 숫자는 소수가 아닙니다.
    // (이 문제에서는 3개의 합이 최소 6 이상이므로 굳이 필요 없지만, 
    // 소수 판별 함수의 완전성을 위해 넣어두는 것이 좋습니다.)
    if (num <= 1) return false;

    // 2. 2부터 num의 제곱근(i * i <= num)까지만 검사합니다.
    // 굳이 모든 숫자를 다 나눠볼 필요 없이, 나누어 떨어지는 수가 하나라도 있다면
    // 즉시 소수가 아님(false)을 반환하고 함수를 종료하여 실행 시간을 아낍니다.
    for (int i = 2; i * i <= num; i++) {
        if (num % i == 0) {
            return false; // 약수가 발견되었으므로 소수가 아님!
        }
    }

    // 3. 위의 반복문을 무사히 통과했다면 약수가 없다는 뜻이므로 소수(true)입니다.
    return true;
}

int solution(vector<int> nums) {
    int answer = 0; // 소수가 되는 경우의 수를 누적할 변수
    int total = 0;  // 3개 숫자의 합을 임시로 저장할 변수

    // nums.size() == 3 인 경우의 예외 처리를 지웠습니다.
    // 아래 3중 for문은 배열의 크기가 3이어도 조건에 맞게 딱 1번만 순회합니다.

    // 1번 숫자 선택 (마지막 두 자리를 남겨둬야 하므로 nums.size() - 2 까지)
    for (int i = 0; i < nums.size() - 2; i++) {
        
        // 2번 숫자 선택 (1번 숫자 다음부터 시작, 마지막 한 자리를 남겨둬야 함)
        for (int j = i + 1; j < nums.size() - 1; j++) {
            
            // 3번 숫자 선택 (2번 숫자 다음부터 배열의 끝까지)
            for (int k = j + 1; k < nums.size(); k++) {
                
                // 선택된 서로 다른 3개의 숫자를 더합니다.
                total = nums[i] + nums[j] + nums[k];

                // 더한 값(total)이 소수인지 판단 함수를 호출하여 확인합니다.
                if (isPrime(total)) {
                    answer++; // 소수라면 경우의 수를 1 증가시킵니다.
                }
            }
        }
    }

    return answer; // 최종 누적된 소수의 개수 반환
}

주요 리팩토링 포인트

1. 소수 판별 함수(Prime Check)의 비약적인 속도 개선

기존의 PrimeNum 함수는 1부터 num까지 모든 숫자로 나누어보며 확인합니다. (시간 복잡도 $O(N)$)

하지만 수학적으로 어떤 수 $N$의 약수들은 항상 $\sqrt{N}$ (제곱근)을 기준으로 짝을 이룹니다.

따라서 1과 자기 자신을 제외하고, 2부터 $\sqrt{N}$까지만 나누어 떨어지는지 검사하면 검사 횟수를 획기적으로 줄일 수 있습니다. (시간 복잡도 $O(\sqrt{N})$)

2. 불필요한 예외 처리(if-else) 제거

nums.size() == 3일 때를 위해 따로 작성하신 코드는, 사실 아래쪽에 있는 3중 for문이 스스로 완벽하게 처리할 수 있는 범위입니다. 배열 크기가 3이면 3중 반복문이 정확히 딱 한 번만 실행되기 때문입니다. 이 부분을 제거하면 코드가 훨씬 간결해집니다.

3. 직관적인 네이밍

함수 이름을 PrimeNum(명사형)에서 isPrime(논리형/동사형)으로 변경하여, 이 함수가 true/false를 반환한다는 것을 이름만 보고도 알 수 있게 했습니다.

---

회고

문제를 풀며 시간복잡도를 고려해서 구현해 봤는데, 더 단축시킬 수 있는법을 AI를 통해 알 수 있었다. Solution 함수의 입력 vector사이즈가 3개일때와 아닐때를 구별하였는데 그 부분을 for문이 이미 가지고 있는 로직이였고, 소수 판별 함수에서 굳이 모든 수로 나눠 볼것이 아니라 2번이상이 나오면 탈출하는 구문으로 시간을 더 단축할 수 있음을 알 수 있었다.