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

 

이번 포스팅에서는 소수를 판별하는 로직과, 재귀를 이용한 조합을 사용해서

배열 내의 값을 조작해서 소수를 만들 수 있는지 없는지에 대한 문제를 풀어보도록 하겠습니다.

문제는 아래 링크에 있습니다.

 

[ 문제 ] 프로그래머스: 소수 만들기

https://programmers.co.kr/learn/courses/30/lessons/12977

코딩테스트 연습 - 소수 만들기

 

 

[ 나의 풀이 ]

#include <vector>
#include <iostream>
#include <math.h>
#define PICK 3
using namespace std;

int answer = 0; // 소수가 되는 경우의 개수

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

void Comb(vector<int> nums, vector<int> comb, int index, int depth){
    if (depth == PICK){
        int sum = 0;
        for (int i=0; i < PICK; i++) {
            sum += comb[i];
        }
        
        if (isPrime(sum))
            answer++;
        
        return;
    } else {
        for (int i=index; i < nums.size(); i++){
            comb[depth] = nums[i];
            Comb(nums, comb, i+1, depth+1);
        }
    }
}


int solution(vector<int> nums) {
    
    vector<int> comb(PICK);
    
    Comb(nums, comb, 0, 0);

    return answer;
}

 

[ 풀이 설명 ]

1. PICK이라는 매크로는 nums 배열 중에서 3개를 뽑기 때문에, 3이라고 정의해 주었다.

2. 초기 main에서 comb라는 int형 vector를 PICK 개수만큼 선언해준다.

3. Comb 함수를 호출하면서 nums배열과, 방금 생성한 PICK개의 빈 vector를 그리고 시작 index와 깊이(원소를 pick한 개수)를 인자로 넘겨준다.

4. Comb 함수 안에서는 재귀적으로 수행되며 N개중에 PICK(3)개를 뽑는 과정이 있고, depth == PICK 조건이 만족되어지면 3개를 다 골랐다는 의미이고, 해당 조건문에서 원소들의 합을 구한다.

5. 만약 구한 합(sum)이 isPrime 함수를 통해 소수임이 판별되어지면 구하고자 하는 최종 답인 answer 변수 값을 증가

6. 그러면 answer에는 우리가 구하고자 하는 N개의 배열 중에서 3개를 뽑아 더해 만든 수가 소수인 개수가 들어있다.

 

 

[ 실행 결과 ]

 

 

[ 다른 사람 풀이 ]

#include <vector>
#include <iostream>
using namespace std;
bool check(int n){
    for(int i=2;i<n/2;i++)
        if(n%i==0)
            return false;
    return true;
}
int solution(vector<int> nums) {
    int answer = 0;
    int N=nums.size();
    for(int i=0;i<N;i++)
        for(int j=i+1;j<N;j++)
            for(int k=j+1;k<N;k++){
                if(check(nums[i]+nums[j]+nums[k]))
                    answer++;
            }
    return answer;
}