[c++] 프로그래머스 :: 소수 찾기 (brute force)

 

https://programmers.co.kr/learn/courses/30/lessons/42839

코드

#include <string>
#include <vector>
#include <set>
#include <algorithm>

using namespace std;

set<int> res;

void test(int num) {
    if (num <= 1)
        return;
    else if (num == 2 || num == 3) {
        res.insert(num);
        return;
    }

    for (int i = 2; i < (int)sqrt(num) + 1; i++) { // num / 2 => num이 최대 9999999 (10^7)
        if (num%i == 0)
            return;
    }
    res.insert(num);
    return;
}

void makePrime(vector<int>& memo,int num) {
    if (memo.size()==0)
        return;

    int size = memo.size();
    for (int i = 0; i < size; i++) { // 7
        int value = memo[i];
        test(num * 10 + value); // 10^7
        memo.erase(memo.begin() + i);
        makePrime(memo, num * 10 + value);
        if (memo.size() == 0)
            memo.push_back(value);
        else
            memo.insert(memo.begin() + i, value);
    }
}

int solution(string numbers) {
    vector<int> memorize;

    for (int i = 0; i < numbers.length(); i++)
        memorize.push_back(numbers[i]-'0');

    makePrime(memorize, 0); //10^8

    int answer = res.size();
    return answer;
}

알고리즘 설명

1. memorize 배열에 입력된 수들을 받는다.

   요소 하나하나가 하나의 조각

2. makePrime 함수에서 재귀적으로 동작한다.

   아직 사용되지 않은 조각, 현재 만들어진 수 를 매개변수로 넘기고 함수에서는 아직 사용되지 않은 조각을 순차적으로 꺼내어 재귀함수를 호출한다.

3. test 함수에서 소수인지 판별한다.

   makePrime함수에서 만든 num이 소수인지 판별해주는 모듈함수.

   그냥 2부터 sqrt(num)까지 돌려보면서 num이 해당 수로 나누어지는 지 본다. 나누어진다면 소수가 아니므로 false를 return한다.

시간 복잡도

10^8 정도 (brute force 가능하다.)