小数点を検索
|問題説明|
一桁と書かれた紙片が散らばっている.ばらばらの紙切れを貼って、いくつかの小数点を作ることができることを見たいです.
1つの解の関数を完成して、いくつかの紙片を作ることができる関数を返します.
_ numbers : 길이 1 이상 7 이하, 문자열
_ numbers : 0~9, 숫자
_ 013은 0, 1, 3 숫자가 적힌 종이 조각이 흩어져있다는 의미
||トラブルシューティング|
- bfs로 숫자를 가지고 만들 수 있는 모든 경우를 탐색 및 저장
- 만들어진 숫자들이 소수인지 체크
|コード|
[20.0.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()함수 대신에 각 문자하나하나에 '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;
}
Reference
この問題について(小数点を検索), 我々は、より多くの情報をここで見つけました https://velog.io/@yerin6860/완전탐색-소수-찾기-wujotphoテキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol