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

문제

소수 만들기 : 문제 링크

문제 분석

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

• 제한 사항

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

• 소수는 1보다 크며 1 이외의 자신으로만 나누어지는 수이다. 따라서 소수 판별을 하기위한 bool형 함수 check를 초기화. 소수는 1보다 커야하므로 if문을 사용하여 매개변수 n이 2미만이라면 false를 return. for loop의 초기화식을 i = 2, 조건식을 i * i <= n로 설정하여 불필요한 연산량을 줄임. loop 순회중 n을 i로 나눈 나머지가 0이라면 false를 return. loop를 탈출했다면 소수임을 의미하므로 true를 return
• solution 함수에서는 3개의 숫자 합이 소수가 되는 경우의 수를 저장할 answer을 0으로, 3개의 숫자 합을 저장할 sum을 초기화. 3중 for loop를 사용하여 각 초기화 식을 i = 0, j = i + 1, z = j + 1로 하여 겹치지 않도록 설정. loop를 순회하면서 배열 nums의 i, j, z 인덱스의 원소의 합을 sum에 저장하고, check 함수를 통해 소수 판별. if문을 사용하여 소수하면 answer을 1씩 늘림. loop 탈출 후, 최종적으로 저장된 answer을 return

풀이

#include <vector>

using namespace std;

bool check(int n) {
    if(n < 2) return false;
    for(int i = 2; i * i <= n; ++i) {
        if(n % i == 0) return false;
    }
    return true;
}

int solution(vector<int> nums) {
    int answer = 0, sum;
    
    for(int i = 0; i < nums.size(); ++i) {
        for(int j = i + 1; j < nums.size(); ++j) {
            for(int z = j + 1; z < nums.size(); ++z) {
                sum = nums[i] + nums[j] + nums[z];
                if(check(sum)) answer++;
            }
        }
    }
    return answer;
}