[Programmers](高得点KIT)完全探索-小数点を探す
12686 ワード
https://programmers.co.kr/learn/courses/30/lessons/42839
問題の説明
一桁と書かれた紙片が散らばっている.ばらばらの紙切れを貼って、いくつかの小数点を作ることができることを見たいです.
各紙片の数字の文字シリアル番号を指定すると、紙片で作成できるいくつかの数を返すための解法関数を完了します.
せいげんじょうけん
numbersは、長さが1または7未満の文字列です.
numbersは0から9まで数字で構成されています.
「013」とは、0から3の数字の紙切れが散らばっていることを意味します.
I/O例
numbersreturn"17"3"011"2
Solution
したがって、stoiによってint型に値を変換すると、少数の面uoreded setに入れる.セットに入れても構いませんが、順序が不要でどうしても繰り返しが許されないので、セットを書いても無秩序セットを書いても、あまり関係ありません.
その名の通り、これは完全な探索なので、できるだけすべての数字を検索すればいいのです.もっと高級に実施してもらえますか?プログラマーのレベルを上げることができるのではないでしょうか.
問題の説明
一桁と書かれた紙片が散らばっている.ばらばらの紙切れを貼って、いくつかの小数点を作ることができることを見たいです.
各紙片の数字の文字シリアル番号を指定すると、紙片で作成できるいくつかの数を返すための解法関数を完了します.
せいげんじょうけん
numbersは、長さが1または7未満の文字列です.
numbersは0から9まで数字で構成されています.
「013」とは、0から3の数字の紙切れが散らばっていることを意味します.
I/O例
numbersreturn"17"3"011"2
Solution
#include <algorithm>
#include <unordered_set>
#include <cmath>
using namespace std;
int isPrime(int N){
if(N == 0 || N == 1) return 0;
for(int i = 2; i <= sqrt(N); i++){
if(N % i == 0) return 0;
}
return 1;
}
int solution(string numbers){
unordered_set<int> uos;
sort(numbers.begin(), numbers.end());
do{
for(int i = 1; i < numbers.size() + 1; i++){
int x = stoi(numbers.substr(0, i));
if(isPrime(x)) uos.insert(x);
}
}while(next_permutation(numbers.begin(), numbers.end()));
return uos.size();
}
簡単です.無秩序setとnext permutationを利用すればよい.int isPrime(int N){
if(N == 0 || N == 1) return 0;
for(int i = 2; i <= sqrt(N); i++){
if(N % i == 0) return 0;
}
return 1;
}
まず、小数であるか否かを判別する関数については説明を省略する.明らかすぎるからint solution(string numbers){
unordered_set<int> uos;
sort(numbers.begin(), numbers.end());
do{
for(int i = 1; i < numbers.size() + 1; i++){
int x = stoi(numbers.substr(0, i));
if(isPrime(x)) uos.insert(x);
}
}while(next_permutation(numbers.begin(), numbers.end()));
return uos.size();
}
まず数字を並べてみます.そして各数字を使って、その名の通り、シーケンスを抽出してから回します.1個引くと、1個からnumberサイズ、例えば4個のカードがあるので1234と入力すると、1から4まで先に引く.もちろんnext permutationは変換されているのでnumbers内の可能なすべての数字で選択できます.したがって、stoiによってint型に値を変換すると、少数の面uoreded setに入れる.セットに入れても構いませんが、順序が不要でどうしても繰り返しが許されないので、セットを書いても無秩序セットを書いても、あまり関係ありません.
その名の通り、これは完全な探索なので、できるだけすべての数字を検索すればいいのです.もっと高級に実施してもらえますか?プログラマーのレベルを上げることができるのではないでしょうか.
Reference
この問題について([Programmers](高得点KIT)完全探索-小数点を探す), 我々は、より多くの情報をここで見つけました https://velog.io/@sierra9707/Programmers-고득점KIT-완전탐색-소수-찾기テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol