Study hard
(c++) 프로그래머스 코딩테스트 연습 - 소수 찾기 본문
programmers.co.kr/learn/courses/30/lessons/42839
[풀이]
dfs순열을 이용하여 나올 수 있는 모든 수에 대해 소수인지 확인하고, set 자료구조를 써서 중복값이 없도록 하였다.
소수는 에라토스테네스의 체를 사용하여 미리 1이상 9999999이하의 모든 소수를 찾아두었다.
<에라토스테네스의 체>
2020/06/18 - [백준/여러가지 문제들] - (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;
}
'프로그래머스 > 완전탐색' 카테고리의 다른 글
(c++)프로그래머스 코딩테스트 연습 - 카펫 (0) | 2020.10.20 |
---|---|
(c++) 프로그래머스 코딩테스트 연습 - 모의고사 (0) | 2020.10.19 |