[ 프로그래머스 ] 소수 찾기

문제

---

https://school.programmers.co.kr/learn/courses/30/lessons/42839

풀이

---

종이 조각을 통해 만들 수 있는 소수의 개수를 구하는 문제로, 만들 수 있는 모든 숫자를 DFS를 통해 만들고, 찾은 소수의 배수를 지워나가는 방식인 에라토스테네스의 체를 통해 일정 범위 내의 모든 소수를 구해, DFS로 만든 숫자 중 소수인 경우만 카운트 해 return한다.

#include <string>
#include <vector>
#include <algorithm>
#include <map>
#include <cmath>

using namespace std;

string target_num;

vector<string> v;

int number = 10000000; // 구하고자 하는 소수의 범위
int primeNum[10000000];

void primeNumberSieve()
{
    // primeNum 배열 초기화
    for (int i = 2; i <= number; i++)
    {
        primeNum[i] = i;
    }

    for (int i = 2; i <= sqrt(number); i++)
    {
        // primeNum[i] 가 0이면 이미 소수가 아니므로 continue
        if (primeNum[i] == 0)
            continue;
        // i*k (k<i) 까지의 수는 이미 검사했으므로 j는 i*i 부터 검사해준다.
        for (int j = i * i; j <= number; j += i)
            primeNum[j] = 0;
    }
}

bool isVisit[8] = { false };

void DFS(string cur_s, int idx)
{
    if (cur_s.size() > target_num.size())
    {
        return;
    }

    if (isVisit[idx - 1] == true && cur_s.size() > 0)
    {
        v.push_back(cur_s);
    }

    for (int i = 0; i < target_num.size(); i++)
    {
        if (isVisit[i] == true)
        {
            continue;
        }

        else
        {
            isVisit[i] = true;
            DFS(cur_s + target_num[i], i + 1);
            isVisit[i] = false;
        }

    }


}

int solution(string numbers) 
{
    int answer = 0;

    string cur_s = "";
    target_num = numbers;

    DFS(cur_s, 0);

    map<string, int> m;

    for (int i = 0; i < v.size(); i++)
    {
        while (v[i][0] == '0')
        {
            if (v[i].size() == 1)
            {
                break;
            }

            else
            {
                v[i].erase(v[i].begin());
            }
        }

        if (v[i] != "0")
        {
            m.insert({ v[i], i });
        }
    }

    primeNumberSieve();

    for (auto iter = m.begin(); iter != m.end(); iter++)
    {
        int num = stoi(iter->first);

        if (primeNum[num] != 0)
        {
            answer++;
        }
    }

    return answer;
}