[완전탐색] 소수 찾기
|| 문제설명 ||
-
한자리 숫자가 적힌 종이 조각이 흩어져있습니다. 흩어진 종이 조각을 붙여 소수를 몇 개 만들 수 있는지 알아내려 합니다.
-
종이 조각으로 만들 수 있는 소수가 몇 개인지 return 하도록 solution 함수를 완성하라.
- numbers : 각 종이 조각에 적힌 숫자가 적힌 문자열
_ numbers : 길이 1 이상 7 이하, 문자열
_ numbers : 0~9, 숫자
_ 013은 0, 1, 3 숫자가 적힌 종이 조각이 흩어져있다는 의미
|| 문제해결방법 ||
- bfs로 숫자를 가지고 만들 수 있는 모든 경우를 탐색 및 저장
- 만들어진 숫자들이 소수인지 체크
|| 코드 ||
[2020.09.26] 실패
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
vector<string> num;
void bfs(string numbers, string n, vector<bool> chk) {
num.push_back(n);
for(int i = 0; i < numbers.size(); i++) {
if(chk[i]) {
chk[i] = false;
bfs(numbers, n + numbers[i], chk);
chk[i] = true;
}
}
}
int find(int num) {
if(num == 1) return 0;
for(int i = 2; i <= num/2; i++) {
if(num % i == 0) return 0;
}
return 1;
}
int solution(string numbers) {
int answer = 0; string n = "";
vector<bool> chk(numbers.size(), true);
for(int i = 0 ; i < numbers.size(); i++) {
chk[i] = false;
if(numbers[i] == '0') bfs(numbers, n, chk);
else bfs(numbers, n + numbers[i], chk);
chk[i] = true;
}
sort(num.begin(), num.end());
answer += find(stoi(num[0]));
for(int i = 1; i < num.size(); i++) {
if(num[i] != num[i - 1]) {
int a = stoi(num[i]);
answer += find(a);
}
}
return answer;
}
#include <string>
#include <vector>
using namespace std;
vector<int> num;
int c[10000000] = {0};
void bfs(string numbers, string n, vector<bool> chk) {
int a = stoi(n);
if(!c[a]) {
num.push_back(a);
c[a] = 1;
}
for(int i = 0; i < numbers.size(); i++) {
if(chk[i]) {
chk[i] = false;
bfs(numbers, n + numbers[i], chk);
chk[i] = true;
}
}
}
int find(int num) {
if(num == 1) return 0;
for(int i = 2; i <= num/2; i++) {
if(num % i == 0) return 0;
}
return 1;
}
int solution(string numbers) {
int answer = 0; string n = "";
vector<bool> chk(numbers.size(), true);
for(int i = 0 ; i < numbers.size(); i++) {
chk[i] = false;
if(numbers[i] == '0') bfs(numbers, n, chk);
else bfs(numbers, n + numbers[i], chk);
chk[i] = true;
}
for(int i = 0; i < num.size(); i++) {
answer += find(num[i]);
}
return answer;
}
- stoi()함수에서의 오류....
[2020.09.29] 성공
- stoi()함수 대신에 각 문자하나하나에 '0'을 빼주어 int값으로 변형
#include <string>
#include <vector>
using namespace std;
vector<int> num;
int c[10000000] = {0};
// numbers의 문자로 만들 수 있는 모든 경우의 수
void bfs(string numbers, string n, vector<bool> chk) {
int a = 0;
// 문자 n을 int형 숫자로 만들어주는 과정
for(int i = 0; i < n.size(); i++) {
if(!a) a = n[i] - '0';
else a = 10 * a + n[i] - '0';
}
// 중복되는 경우 제거
if(!c[a]) {
num.push_back(a);
c[a] = 1;
}
// 사용하지 않은 문자를 추가하여 bfs함수 호출
for(int i = 0; i < numbers.size(); i++) {
if(chk[i]) {
chk[i] = false;
bfs(numbers, n + numbers[i], chk);
chk[i] = true;
}
}
}
// 소수 찾기 : 소수이면 1을 반환
int find(int num) {
if(num == 1 || num == 0) return 0;
for(int i = 2; i <= num/2; i++) {
if(num % i == 0) return 0;
}
return 1;
}
int solution(string numbers) {
int answer = 0; string n = "";
vector<bool> chk(numbers.size(), true);
for(int i = 0 ; i < numbers.size(); i++) {
chk[i] = false;
if(numbers[i] == '0') bfs(numbers, n, chk);
else bfs(numbers, n + numbers[i], chk);
chk[i] = true;
}
for(int i = 0; i < num.size(); i++) {
answer += find(num[i]);
}
return answer;
}
Author And Source
이 문제에 관하여([완전탐색] 소수 찾기), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@yerin6860/완전탐색-소수-찾기-wujotpho저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)