(c++) 프로그래머스 코딩테스트 연습 - 소수 찾기

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

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

[풀이]

dfs순열을 이용하여 나올 수 있는 모든 수에 대해 소수인지 확인하고, set 자료구조를 써서 중복값이 없도록 하였다.

소수는 에라토스테네스의 체를 사용하여 미리 1이상 9999999이하의 모든 소수를 찾아두었다.

<에라토스테네스의 체>

2020/06/18 - [백준/여러가지 문제들] - (c++)백준 1929번: 소수 구하기

(c++)백준 1929번: 소수 구하기

#include <string>
#include <vector>
#include <cstring>
#include <set>

using namespace std;

const int Max = 10000000;
bool Prime[Max];
string Numbers;
vector<char>v;
set<int>p;
bool check[7];
int cnt = 0;

//에라토스테네스의 체
void makePrime() {
	Prime[1] = false;
	for (int i = 2; i < Max / 2; i++) {
		if (Prime[i] == false)
			continue;
		for (int j = i + i; j < Max; j += i) {
			Prime[j] = false;
		}
	}
}

//소수인지 확인
void Check() {
	if (v[0] == '0')
		return;
	int realNum = 0;
	if (v.size() == 1) {
		realNum = v[0] - '0';
	}
	else if (v.size() > 1) {
		for (int i = 0; i < v.size(); i++) {
			realNum = realNum * 10 + (v[i] - '0');
		}
	}
	if (Prime[realNum] == true)
		p.insert(realNum);
}

//가능한 모든 경우의 수 확인(순서 상관O)
void getPrime(int count) {
	if (count > 0)
		Check();
	for (int i = 0; i < Numbers.size(); i++) {
		if (check[i] == true)
			continue;
		check[i] = true;
		v.push_back(Numbers[i]);
		getPrime(count + 1);
		check[i] = false;
		v.pop_back();
	}
}

int solution(string numbers) {
	int answer = 0;
	Numbers = numbers;
	memset(Prime, true, sizeof(Prime));
	makePrime();
	getPrime(0);
	answer = p.size();

	return answer;
}

+ 위의 풀이는 string을 char로 쪼개서 번거롭게 확인했는데, 그냥 stoi쓰는게 편하다..(시간은 위의 방법이 덜 걸린다)

#include <string>
#include <vector>
#include <cstring>
#include <iostream>

using namespace std;
#define Max 10000000


string Num;
int len;
bool Pick[7];
bool Prime[Max];//소수 찾아두기
int prime=0;
bool check[Max];

void getPrime(){
    memset(Prime,true,sizeof(Prime));
    Prime[0]=false;
    Prime[1]=false;
    for(int i=2;i<=Max/2;i++){
        for(int j=i+i;j<=Max;j+=i){
            Prime[j]=false;
        }
    }
}

void dfs(int cnt,string s){
    if(cnt>len)
        return;
    if(cnt>=1){
        int num=stoi(s);
        if(Prime[num]==true){
            if(check[num]==false){
                check[num]=true;
                cout<<num<<' ';
                prime++;
            }
        }
    }
    for(int i=0;i<len;i++){
        if(Pick[i]==true)
            continue;
        Pick[i]=true;
        dfs(cnt+1,s+Num[i]);
        Pick[i]=false;
    }
}

int solution(string numbers) {
    int answer = 0;
    Num=numbers;
    len=numbers.size();
    getPrime();
    dfs(0,"");
    return prime;
}