Programmers: 완전탐색 > 소수 찾기(C++)

https://programmers.co.kr/learn/courses/30/lessons/12921

코딩테스트 연습 - 소수 찾기

풀이법

1) DFS 기반의 알고리즘을 활용하여, 완전 탐색을 통해 문제를 해결 하였다.

2) 첫 번째 값으로는 0이 들어갈 수 없기에 이 부분을 구현해 주었으며, 방문하지 않은 노드들을 방문하며, size를 키워 모든 경우의 수를 탐색하였다.

3) 겹치는 숫자가 없게 담긴 동적 배열 vec에서 소수의 개수를 확인해 주었고 정답을 얻을 수 있었다.

#include <string>
#include <vector>
#include <math.h>
#include <cstring>
#include <algorithm>
using namespace std;
bool visited[7];
vector<int> vec;

void dfs(string a, int size, string numbers) {

	if (a.size() == size) {
		bool check = false;
		for (int i = 0; i < vec.size(); i++)
		{
			if (vec[i] == stoi(a)){
				check = true;
                break;
            }
		}
		if (check == false)
		{
			vec.push_back(stoi(a));
		}
		return;
	}
	else
	{
		for (int i = 0; i < numbers.size(); i++)
		{
			if (visited[i] == false)
			{
				visited[i] = true;
				a += numbers[i];
				dfs(a, size,numbers);
				a.pop_back();
				visited[i] = false;
			}
		}
	}
}

int solution(string numbers) {
    int answer = 0;
    int size = 1;
	while (size <= numbers.size()) {
		string a = "";
		for (int i = 0; i < numbers.size(); i++)
		{
			if (numbers[i]-'0' != 0)
			{
				visited[i] = true;
				a += numbers[i];
				dfs(a, size, numbers);
				a.pop_back();
				visited[i] = false;
			}
		}
		size++;
	}
    //소수 찾기
    for(int i=0; i<vec.size();i++)
    {
        if(vec[i]==1)
            continue;
        bool check=false;
        for(int j=2;j<=sqrt(vec[i]);j++)
        {
            if(vec[i]%j==0){
                check=true;
                break;
            }
        }
        if(check==false)
            answer++;
    }
    return answer;
}