Programers 소수찾기

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

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

프로그래머스 소수찾기 문제입니다.

#include <string>
#include <vector>
#include <bitset>
using namespace std;

string num, paper;
int len;
int cnt;
vector<int> nums;
bool use[7];
bitset<(1 << 25)> bit;

bool isPrime(int n) {
	if (n < 2) return false;
	for (int i = 2; i*i <= n; i++) {
		if (n%i == 0) return false;
	}
	return true;
}

void dfs(int n) {
	if (n == len)
		return;
	for (int i = 0; i < len; i++) {
		if (use[i]) continue;
		num += paper[i];
		if (bit[stoi(num)])
			if (isPrime(stoi(num)))
				cnt++;
		use[i] = true;
		bit[stoi(num)] = 0;
		dfs(n + 1);
		use[i] = false;
		num.pop_back();
	}
}

int solution(string numbers) {
	
	fill(use, use + 7, false);
	bit.set();
	paper = numbers;
	len = paper.length();
	for (int i = 0; i < len; i++)
		dfs(0);
	int answer = cnt;
	return answer;
}

아이디어

완전탐색문제에 숫자를 사용해서 이전에 써봤던 bitset을 이용하여 중복을 처리했고, DFS로 탐색, 소수 검사 부분은 에라토스테네스의 체를 이용했음

주의점은 i*i<n -> i*i<=n 실수하면 틀린곳 찾기가 힘들어짐