[2025.01.28] 소수 만들기

문제 설명

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

 

 

제한사항

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

 

 

입출력 예

nums			result	설명
[1, 2, 3, 4]			1	[1, 2, 4]를 이용해서 7을 만들 수 있습니다.
[1, 2, 7, 6, 4]			4	[1, 2, 4]를 이용해서 7을 만들 수 있습니다. [1, 4, 6]을이용해서 11을 만들 수 있습니다. [2, 4, 7]을 이용해서 13을 만들 수 있습니다. [4, 6, 7]을 이용해서 17을 만들 수 있습니다.

 

 

문제 풀이

풀이 언어 : C++

#include <vector>
using namespace std;

bool is_prime_num(int num)
{
    // 2인 경우 소수
    if(num==2)
    {
        return true;
    }
    
    // 2가 아닌 경우 소수 검사
    for(int i=2; i<num; i++)
    {
        // 1과 자기 자신만이 아닌 다른 수로 나누어 진다면
        if(num%i==0)
        {
            return false; // 소수
        }
    }
    
    return true;
}

int solution(vector<int> nums) {
    int answer = 0;
    
    // 3개의 수 더하기
    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++)
            {
                // 3개의 수를 더한게 소수라면
                if(is_prime_num(nums[i]+nums[j]+nums[k]))
                {
                    answer++; // answer 업데이트
                }
            }
        }
    }
    
    return answer;
}

두 개의 기능만 구현하면 풀 수 있는 문제다. 첫째는 벡터 중 중복 없이 3개의 수를 골라내는 기능이고, 둘째는 특정 수가 소수인지 구별해는 것이다.

 

우선 여러 수가 들어있는 벡터에서 세 개의 수를 골라내고 그 수의 합을 구하는 방법이다. 분명 이런 기능을 구현해보았던 기억이 있어서 이전에 풀었던 문제를 찾아보았다.

https://iiblueblue.tistory.com/156

[2025.01.16] 삼총사

for문 세 개를 이용한 방법이다. 가장 큰 반복문은 i=0~nums.size()-2 반복문을 돌리고 중간 반복문은j=i+1~nums.size()-1 반복문을 돌린다. 마지막으로 가장 안쪽에 작은 반복문은 k=j+1~nums.size() 반복문을 돌린다. 이렇게하면 가장 안쪽의 반복문에서 nums[i], nums[j], nums[k]를 이용하면 벡터 안에 모든 수 중 3개를 중복없이 고를 수 있다. 필요한 건 세 수의 합이므로 nums[i]+nums[j]+nums[k]을 이용해 이 수가 소수인지 판별한다.

 

소수임을 판별하기 위해 is_prime_num(int num) 함수를 만들어서 사용한다. 우선 2는 소수로 먼저 분리해준다. 2가 아닌 나머지의 수는 반복문을 이용해 소수임을 판별한다. for문을 이용해 2부터 num-1까지의 수로 num을 나누어 나머지를 확인한다. 나누어 떨어진다면 false를 반환해 소수가 아님을 나타내고 반복문이 돌아가는 동안 나누어 떨어지는 수가 없으면 마지막에 true를 반환해 소수임을 반환한다.

 

반복문의 안에서 is_prime_num을 이용해서 소수인지 확인하고 소수일 경우 answer++을 하여 수를 업데이트 한다. 소수가 아닐 경우 아무 것도 하지 않는다.

 

 

문제 링크

https://school.programmers.co.kr/learn/courses/30/lessons/12977?language=cpp

프로그래머스