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

프로그래머스의 소수찾기(Lv2) 문제이다.

[ 문제풀이 ]

1) 본인은 이 문제를 부분집합의 개념으로 접근해 보았다.

   주어진 문자열에서, 구할 수 있는 모든 원소들을 순열의 개념으로 뽑으면서 그 뽑은 값들이 소수인지 아닌지

   판단해 주었다.

   순열의 개념을 사용한 이유는, "17"이 있을 때, "1" + "7"과, "7" + "1"은 서로 다른 결과를 가져오기 때문에

   순서에 영향을 미친다는 것을 알 수 있다.

   [ 순열에 대한 개념 및 구현법 알아보기 (Click) ]

  

   또한, 방문체크를 해주는 배열을 만들어서 이미 방문한 숫자는 카운트 되지 않도록 만들어 주었다.

   Visit[a] = true 의 의미는 숫자 "a"는 이미 방문한 적이 있습니다. 를 의미한다.

   또한 해당 숫자가 소수인지 아닌지 판단할 때에는, 해당 숫자 까지가 아닌 루트를 씌운 값 까지만 계산을 해주면 된다.

   예를 들어서 31 이라는 숫자가 있을 때, 2 ~ 31 까지 31로 나누어 떨어지는 숫자가 있는지 찾아보는 것 보다,

   루트를 씌운 루트31까지의 값 까지만 비교해도 소수인지를 찾을 수 있다.

   루트 31은 약 5.xxx 일 것이다. 이는, 2, 3, 4, 5 어떤 수로도 나누어 떨어지지 않기 때문에 소수라는 것을

   알 수 있다.

  

[ 소스코드 ]

#include<string>
#include<vector>
#include<cmath>
 
using namespace std;
 
bool Visit[10000000];
bool Select[10];
int Answer;
 
bool IsPrime(int N)
{
    if (N == 0 || N == 1) return false;
 
    for (int i = 2; i <= sqrt(N); i++)
    {
        if (N % i == 0) return false;
    }
    return true;
}
 
void DFS(int Cnt, string S, string Res)
{
    if(Res != "" && Visit[stoi(Res)] == false)
    {
        int Num = stoi(Res);
        Visit[Num] = true;
        if (IsPrime(Num) == true) Answer++;
    }
 
    for (int i = 0; i < S.length(); i++)
    {
        if (Select[i] == true) continue;
        Select[i] = true;
        DFS(Cnt + 1, S, Res + S[i]);
        Select[i] = false;
    }
}
 
int solution(string S)
{
    DFS(0, S, "");
    return Answer;
}