프로그래머스 12977 - 소수 만들기

https://programmers.co.kr/learn/courses/30/lessons/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

 

Python

from itertools import combinations
from math import sqrt

def IsPrime(num):
    for i in range(2, int(sqrt(num) + 1)):
        if num % i == 0:
            return False
    return True

def solution(nums):
    answer = 0
    temp = list(combinations(nums, 3))
    for i in temp:
        if IsPrime(sum(i)):
            answer += 1

    return answer

combinations(list, 갯수) 로 하면 Tuple이 나오는데 list랑 별 다를게 없다.

Tuple은 내부 값 변경이 불가능하다는 점 빼면 list와 완전 똑같다. 그래서 sum 함수를 쓸 수 있다.

 

C++

#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;

bool IsPrime(int num) {
    for(int i = 2; i <= sqrt(num); i++){
        if(num % i == 0)
            return false;
    }
    return true;
}

int solution(vector<int> nums) {
    int answer = 0;
    sort(nums.begin(), nums.end());
    
    vector<int> sample;
    int k = 3;
    for (int i = 0; i < k; i++)
    {
        sample.push_back(1);
    }
 
    for (int i = 0; i < nums.size() - k; i++)
    {
        sample.push_back(0);
    }
    sort(sample.begin(), sample.end());
    
    vector<int> vSum;
    do{
        int sum = 0;
        for(int i = 0; i < nums.size(); i++){
            if (sample[i] == 1)
            {
                sum += nums[i];
            }
        }
        if(IsPrime(sum)) {
            answer++;
        }
    }while(next_permutation(sample.begin(), sample.end()));
    
    return answer;
}

algorithm stl안에 next_permutation이라는 순열을 구하는 함수를 활용하여 조합을 구할 수 있다.