[프로그래머스] [C++] 소수 찾기 (brute-force)

1. 문제 

0~9로 이루어진 문자열이 주어진다.

 

적절히 자르고 붙여서 중복되지 않은 숫자를 만드는 경우의 수 중

 

소수인 숫자들의 개수를 구하여라.

 

 

 

2. 에라토스테네스의 체와 브루트 포스(dfs)

일단 나올 수 있는 최대 숫자까지 모든 숫자에대해 소수인지 아닌지 판별하여  전역 변수에 기록하였다.

 

이것은 에라토스테네스의 체의 알고리즘으로 소수를 판별하였다.

 

그 후 입력으로 주어진 문자열을 가공하여 0~9의 개수를 담은 배열을 만들었다.

 

이렇게 배열을 만들고 dfs를 하게되면 한번의 실행에 0~9를 탐색하지만 중복된 숫자를 따로 처리하지 않을 수 있다.

 

dfs로 다른 숫자들을 붙여나가며 소수인지를 판별해나가며 개수를 카운트한다.

 

 

 

 

3. 코드

아쉬운점: 함수명을 dp로 한점

 

#include <string>
#include <vector>
#include <cmath>
#include <cstring>
 
using namespace std;
 
const int MAX_INT = 9999999;
 
bool isPrime[MAX_INT+1];
 
void era()
{
    memset(isPrime, true, sizeof isPrime);
    isPrime[0] = false;
    isPrime[1] = false;
    int size = sqrt(MAX_INT);
    for(int i = 2; i <= size; i++)
        if(isPrime[i]) 
            for(int j = i*i; j <= MAX_INT; j+= i)
                isPrime[j] = false;
}
 
vector<int> makeSet(string& str)
{
    vector<int> ret(10, 0);
    for(int i = 0; i < str.size(); i++)
        ret[(int)str[i] - '0']++;
        
    return ret;
}
 
void dp(vector<int>& numSet, int sum, int& answer)
{
    if(isPrime[sum])
        answer++;
    for(int i = 0; i < 10 ; i++)
    {
        if(numSet[i] == 0 || (i == 0 && sum == 0)) continue;
        
        numSet[i]--;
        dp(numSet, sum*10 + i, answer);
        numSet[i]++;
    }
}
 
int solution(string numbers) {
    int answer = 0;
    era();
    vector<int> numSet = makeSet(numbers);
    dp(numSet,0, answer);
    return answer;
}

programmers.co.kr/learn/courses/30/lessons/42839