소수 찾기

문제 설명

한자리 숫자가 적힌 종이 조각이 흩어져있습니다. 흩어진 종이 조각을 붙여 소수를 몇 개 만들 수 있는지 알아내려 합니다.

 

각 종이 조각에 적힌 숫자가 적힌 문자열 numbers가 주어졌을 때, 종이 조각으로 만들 수 있는 소수가 몇 개인지 return 하도록 solution 함수를 완성해주세요.

 

제한사항

• numbers는 길이 1 이상 7 이하인 문자열입니다.
• numbers는 0~9까지 숫자만으로 이루어져 있습니다.
• "013"은 0, 1, 3 숫자가 적힌 종이 조각이 흩어져있다는 의미입니다.

입출력 예

numbers	return
"17"	3
"011"	2

---

문제 해설

문자열이 string형태로 제공되어있다. string을 stoi로 변환하여 사용해야 함을 뜻함.

 

그리고, string내부의 모든 수가 이어질 수 있는 경우의수를 전부 세어 결과에 반영해야 한다는 뜻은 제귀를 통해 수를 연산하는게 효율적 이라는 의미이다. 모든경우의수를 다 탐색하는건 while 또는 제귀가 옳다.

 

내부연산은, 중첩해서 이어진 숫자를 제귀인지 아닌지 판별하면 된다.

제귀판별 연산은, 채 형태로 배열로 저장하고, 비교연산을 하는 방법이 있고, 루트를 씌우고 나온 수까지 for문으로 돌려서 나머지가 나오는지, 루트를 씌우고 나온 수가 정수인지 판별하면 된다.

 

루트를 씌우고 나온 수가 정수라면, 4 같이, 1, 2, 4 로, 같은수로 제곱되어 나오는 수가 있다는 의미 이기때문에 소수가 아님을 알 수 있음.

---

첫 시도

#include <iostream>
#include <string>
#include <vector>
#include <set>
#include <list>
#include <cmath>

using namespace std;

vector<bool> stick;
vector<int> disc;

void AllSearch(set<int>& result, string& numbers, int nowCount = 0, int nownumber = 0)
{
    string numbers_now(numbers);
    nownumber *= 10;
    nownumber += stoi(numbers_now.substr(nowCount, 1));
    numbers_now.erase(nowCount, 1);

    int sticknowsize = stick.size();

    if (sticknowsize < nownumber)
        stick.reserve(nownumber + 1);

    for (int i = sticknowsize; i <= nownumber; i++) {
        bool chack;
        for (auto& def : disc)
        {
            if (i % def == 0)
            {
                chack = false;
                break;
            }
            else
                chack = true;

        }
        if (chack) {
            stick.push_back(true);
            disc.push_back(i);
        }
        else
            stick.push_back(false);
    }

    if (stick[nownumber] == true)
        result.insert(nownumber);

    if (numbers_now.empty()) {
        return;
    }

    for(int i = 0; i < numbers_now.size(); i++)
        AllSearch(result, numbers_now, i, nownumber);
}

int solution(string numbers) {
    int answer = 0;
    set<int> result;
    stick.push_back(false);
    stick.push_back(false);
    stick.push_back(true);
    stick.push_back(true);
    disc.push_back(2);
    disc.push_back(3);

    for (int i = 0; i < numbers.size(); i++)
        AllSearch(result, numbers, i);

    return result.size();
}

실패

데이터 정리는 맞으나, 시간초과가 나타남.

데이터를 전부다 정리해서 저장하려고하다가 이꼴이남.

 

아니 소수를 저장하고싶을 수도 있지 왜그럼

---

두 번째 시도

#include <string>
#include <vector>
#include <set>
#include <cmath>

using namespace std;

void AllSearch(set<int>& result, string& numbers, int nowCount = 0, int nownumber = 0)
{
    string numbers_now(numbers);
    nownumber *= 10;
    nownumber += stoi(numbers_now.substr(nowCount, 1));
    numbers_now.erase(nowCount, 1);

    int count = 0;
    double sq = sqrt(nownumber);
    if(sq != floor(sq))
        for (int i = 1; i < sq; i++) 
            if (nownumber % i == 0)
                count++;

    if (count == 1)
        result.insert(nownumber);

    if (numbers_now.empty()) 
        return;

    for (int i = 0; i < numbers_now.size(); i++)
        AllSearch(result, numbers_now, i, nownumber);
}


int solution(string numbers) {
    int answer = 0;
    set<int> result;
    for (int i = 0; i < numbers.size(); i++)
        AllSearch(result, numbers, i);

    return result.size();
}

성공

그래서 그냥 저장 안하고 그때그때 확인하기로함.

 

확인해야하는 조건이 제곱승이 정수인지?(제곱된 값이 해당값의 곱이 될 수 있기때문에 예외처리)

순차적으로 올라가는 값으로 나눈 값에 나머지가 존재하는지 여부이다.

 

그렇게 값을 전부 확인해서 데이터를 기입하면됨.

 

어차피 중간제곱값 이후로는 곱셈이 전부 연산되어 중첩되기 때문,