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

문제 설명

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

 

제한사항

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

---

입출력 예

numsresult

[1,2,3,4]	1
[1,2,7,6,4]	4

입출력 예 설명

입출력 예 #1
[1,2,4]를 이용해서 7을 만들 수 있습니다.

입출력 예 #2
[1,2,4]를 이용해서 7을 만들 수 있습니다.
[1,4,6]을 이용해서 11을 만들 수 있습니다.
[2,4,7]을 이용해서 13을 만들 수 있습니다.
[4,6,7]을 이용해서 17을 만들 수 있습니다.

---

내 풀이

주어진 nums 배열에서 세 가지 원소를 합하여 만들 수 있는 모든 수를 구하고, 해당 수가 소수인지 판별하여 소수라면 num_prime을 1씩 증가시키는 방식으로 구현하였다.

#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>

int num_prime = 0;

// 소수 판별 함수
int isPrime(int num){
    int last = num / 2;
    
    if(num <= 1)
        return 0; // 1은 소수 X
    
    for(int i = 2; i <= last; i++){ // (num / 2)보다 큰 수는 약수 x
        if((num % i) == 0) // n이 i로 나누어 떨어지면
            return 0; // 소수 X
    }
    
    return 1; // 소수 O
}

void cnt_comb(int count, int copy[]){
    int ans = 0;
    for(int i = 0; i < count; i++){
        ans += copy[i]; // 조합 내 모든 원소의 합
    }
    if(isPrime(ans)) // 세 원소의 합이 소수면
        num_prime++; // num_prime 변수 1 증가
}

// 조합의 모든 경우의 수를 구하는 함수
void comb(int n, int r, int c, int nums[], int copy[]){
    if(r == 0){
        cnt_comb(c, copy);
        return;
    }
    
    if(n < r)
        return;
    else{
        copy[r - 1] = nums[n - 1];
        comb(n - 1, r - 1,  c, nums, copy);
        comb(n - 1, r, c, nums, copy);
    }
}

// nums_len은 배열 nums의 길이입니다.
int solution(int nums[], size_t nums_len) {
    int answer = 0;
    int copy[nums_len];
    
    comb(nums_len, 3, 3, nums, copy);
    
    answer = num_prime;
    
    return answer;
}

조합 함수인 comb의 작동 예시는 아래 이미지와 같다.

comb 함수 작동 예시

좋은 수가 생각나지 않아 비효율을 감수하고 조합을 통해 모든 경우의 수를 구하는 방식으로 구현하였다.

 

하지만 다른 사람들의 풀이를 보니, 애초에 문제 자체가 효율적으로 풀 수 없는 문제인 것 같다.

그래도 내 코드보다 훨씬 간결하여, 아래에 첨부한다.

 

다른 사람의 풀이

#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>
bool checkSoSu(int n) {
    int i=n-1;
    while(i!=1) {
        if(n%i == 0) {
            return false;
        } else i--;
    }

    return true;
}
// nums_len은 배열 nums의 길이입니다.
int solution(int nums[], size_t nums_len) {
    int answer = 0;
    for(int i=0;i<nums_len-2;i++) {
        for(int j=i+1;j<nums_len-1;j++) {
            for(int k=j+1;k<nums_len;k++) {

                if(checkSoSu(nums[i]+nums[j]+nums[k])) answer++;
            }
        }
    }
    return answer;
}