[프로그래머스][C++] 소수 만들기

소수 만들기

문제 링크

소수 만들기

분석

nums에서 요소 3개의 합을 구하고, 소수인지 확인하는 문제입니다.

최종적으로 만들 수 있는 소수의 개수를 반환하면 됩니다.

nums의 요소 중 3개를 선택해야하므로, 브루트포스로 접근해야합니다.

풀이

#include <vector>

using namespace std;

int solution(vector<int> nums) {
    int answer = 0;

    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)
            {
                int num = nums[i] + nums[j] + nums[k];
                
                bool isPrimeNumber = true;
                for (int l = 2; l * l <= num; ++l)
                {
                    if (num % l == 0)
                    {
                        isPrimeNumber = false;
                        break;
                    }
                }
                
                if (true == isPrimeNumber)
                {
                    ++answer;
                }
            }
        }
    }

    return answer;
}

첫 반복문 3개는 nums에서 요소 3개를 선택합니다.

for (int l = 2; l * l <= num; ++l)에서 소수를 구합니다.
l * l은 소수인지 확인 할 때 제곱근이 넘어간 값은 확인할 필요 없으므로 제곱근까지만 확인합니다.

성능 요약

시간 복잡도는 $O(n^3)$의 시간 복잡도를 가집니다.

• 3중 반복문($O(n^3)$)
• 소수를 확인하는 반복문($O(\sqrt m)$)
• $O(n^3 \sqrt m) \approx O(n^3)$

공간 복잡도는 고정된 크기의 상수 공간을 사용하기 때문에 $O(1)$입니다.

테스트 1 〉 통과 (0.07ms, 4.2MB)
테스트 2 〉 통과 (0.08ms, 4.02MB)
테스트 3 〉 통과 (0.02ms, 4.14MB)
테스트 4 〉 통과 (0.02ms, 3.63MB)
테스트 5 〉 통과 (0.11ms, 4.23MB)
테스트 6 〉 통과 (0.21ms, 4.2MB)
테스트 7 〉 통과 (0.01ms, 4.2MB)
테스트 8 〉 통과 (0.44ms, 4.17MB)
테스트 9 〉 통과 (0.03ms, 3.63MB)
테스트 10 〉 통과 (0.32ms, 4.15MB)
테스트 11 〉 통과 (0.01ms, 3.58MB)
테스트 12 〉 통과 (0.01ms, 4.13MB)
테스트 13 〉 통과 (0.01ms, 4.19MB)
테스트 14 〉 통과 (0.01ms, 4.16MB)
테스트 15 〉 통과 (0.01ms, 4.02MB)
테스트 16 〉 통과 (0.48ms, 4.2MB)
테스트 17 〉 통과 (0.06ms, 3.68MB)
테스트 18 〉 통과 (0.01ms, 4.21MB)
테스트 19 〉 통과 (0.01ms, 4.2MB)
테스트 20 〉 통과 (0.59ms, 4.14MB)
테스트 21 〉 통과 (0.55ms, 4.19MB)
테스트 22 〉 통과 (0.02ms, 4.2MB)
테스트 23 〉 통과 (0.01ms, 4.21MB)
테스트 24 〉 통과 (0.47ms, 4.2MB)
테스트 25 〉 통과 (0.48ms, 4.21MB)
테스트 26 〉 통과 (0.01ms, 3.71MB)