프로그래머스 - 소수 찾기

 코딩테스트 고득점 Kit 완전탐색 Level 2 문제 소수 찾기 풀이이다. 이 문제는 string 으로 주어진 0 ~ 9 까지의 숫자를 조합하여 소수가 되는 모든 경우의 수를 구하는 문제이다. 숫자가 아무리 커도 9999999 까지밖에 안되므로 전역 배열 isPrime을 선언하여 에라토스테네스의 체를 이용하여 소수를 구하고, 숫자들의 조합을 완전 탐색으로 구한 뒤 그 숫자가 소수이면 map에 저장하여 최종적으로 map.size() 를 통해 답을 구했다.

 

#include <string>
#include <vector>
#include <map>

using namespace std;

#define MAX 9999999

bool isPrime[MAX + 1];
map<int, int> m;

void makePrime()
{
    for (int i = 2; i <= MAX; i++)
    {
        isPrime[i] = true;
    }
    
    for (int i = 2; i * i <= MAX; i++)
    {
        if (isPrime[i])
        {
            for (int j = i * i; j <= MAX; j += i)
            {
                isPrime[j] = false;
            }
        }
    }
}

void primeDecision(int num)
{
    if (isPrime[num])
    {
        m[num]++;
    }
}

void func(string& numbers, int index, string res, vector<bool>& used)
{
    if (index == numbers.size())
    {
        if (res.empty())
        {
            return;
        }
        
        int temp = stoi(res);
        
        primeDecision(temp);
        
        return;
    }
    func(numbers, index + 1, res, used);
    
    for (int i = 0; i < numbers.size(); i++)
    {
        if (!used[i])
        {
            used[i] = true;
            func(numbers, index + 1, res + numbers[i], used);
            used[i] = false;
        }
    }
}

int solution(string numbers) {
    int answer = 0;
    string res = "";
    vector<bool> used(numbers.size(), false);
    
    makePrime();
    func(numbers, 0, res, used);
    
    answer = m.size();
    
    return answer;
}