프로그래머스 소수찾기

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

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

#include <string>
#include <vector>
#include <iostream>
using namespace std;
vector<int>d;//순열값 저장한곳
int chk[8];//순열 중복 체크
int ret;// 최종값
int numChk[9999999];
bool primNum(int num) {
	if (numChk[num] == 1)return false;
	if (numChk[num] == 0) numChk[num] = 1;
	if (num == 1||num==0)return false;
	for (int i = 2; i*i <= num; i++) {
		if (num%i == 0)return false;
	}
	return true;
}
void dfs(int idx,vector<int> &v ) {
	if (idx == v.size()) return;
	if(d.size()!=0) {
		int sum = 0;//정수형 값 계산되는곳
		int ten = 1;//10씩 증가
		for (int i = 0; i < d.size(); i++) {
			sum += d[i] * ten;
			ten *= 10;
		}
		if (primNum(sum)) {//소수 판별 
			ret++;
		}
		//cout << sum<<endl;
	}
	for (int i = 0; i < v.size(); i++) {
		if (chk[i] == 0) {
			chk[i] = 1;
			d.push_back(v[i]-48);
			dfs(i, v);
			d.pop_back();
			chk[i] = 0;
		}
	}

	
}
int solution(string numbers) {
	int answer = 0;
	vector<int>v;
	for (int i = 0; i < numbers.size(); i++) {
		v.push_back(numbers[i]);
	}
	dfs(0, v);

	return answer=ret;
}
int main(void) {
	//cout << solution("17");
	cout << solution("011");
	//cout << solution("123");
	return 0;
}

이문제는 두가지를 조심하면될것 같다 우선 흩어져있는 수로 숫자를 만들수 있는가 

그리고 소수 판별을 할줄 아는가 여기의 경우는 소수판별을 일반적으로 해도 통과가 되었다.

일반적으로 했을때의 속도는 이렇다.

 

그리고 좀 소수 판별에 대해서 최적화를 하면 이렇다.

대게 테스트 케이스에서 개선된것을 볼수 있다 특히 테스트 2번에서는 획기적으로 속도가 개선된것이 보인다.

그런 점을 조심해주면 좋을것 같다.

#include <string>
#include <vector>
#include <iostream>
using namespace std;
vector<int>d;//순열값 저장한곳
int chk[8];//순열 중복 체크
int ret;// 최종값
int numChk[9999999];
bool primNum(int num) {
	if (numChk[num] == 1)return false;
	if (numChk[num] == 0) numChk[num] = 1;
	if (num == 1||num==0)return false;
	for (int i = 2; i*i <= num; i++) {
		if (num%i == 0)return false;
	}
	return true;
}
void dfs(int idx,vector<int> &v ) {
	if (idx == v.size()) return;
	if(d.size()!=0) {
		int sum = 0;//정수형 값 계산되는곳
		int ten = 1;//10씩 증가
		for (int i = 0; i < d.size(); i++) {
			sum += d[i] * ten;
			ten *= 10;
		}
		if (primNum(sum)) {//소수 판별 
			ret++;
		}
		//cout << sum<<endl;
	}
	for (int i = 0; i < v.size(); i++) {
		if (chk[i] == 0) {
			chk[i] = 1;
			d.push_back(v[i]-48);
			dfs(i, v);
			d.pop_back();
			chk[i] = 0;
		}
	}

	
}
int solution(string numbers) {
	int answer = 0;
	vector<int>v;
	for (int i = 0; i < numbers.size(); i++) {
		v.push_back(numbers[i]);
	}
	dfs(0, v);

	return answer=ret;
}
int main(void) {
	//cout << solution("17");
	cout << solution("011");
	//cout << solution("123");
	return 0;
}