[프로그래머스][C++] 소수 찾기

 

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

코딩테스트 연습 - 소수 찾기

 

글쓴이의 답

개인적인 풀이 임으로

이것보다 더 좋은 알고리즘은 많음...

이렇게도 풀이하는구나.. 공유하기 위해 올림...

 

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

using namespace std;

bool getResult(int num){
    
    bool result = false;
    
    if(num <= 1){
        result = true;
        return result;
    }
    
    if(num == 2){
        result = false;
        return result;
    }
    
    for(int i=2; i <= num/2; i++){
        if(0 == num%i){
            result = true;
            break;
        }
    }
    
    return result;
}

int dfs(vector<bool> &check, int location, string &numbers, string &result, set<int> &resultSave){
    
    int temp = stoi(result);
    resultSave.insert(temp);
    
    for(int i=0; i< numbers.size(); i++){
        if(true == check[i]){
            continue;
        }
        check[i] = true;
        result+=numbers[i];
        dfs(check, i, numbers, result, resultSave);
        result.pop_back();
        check[i] = false;
    }
    
    return 0;
}

int solution(string numbers) {
    int answer = 0;
    size_t numSize = numbers.size();
    vector<bool> check(numSize, false);
        
    set<int> resultData;    
    string result="";
    for(int i=0; i< numbers.size(); i++){        
        check[i] = true;
        result+=numbers[i];
        dfs(check, i, numbers, result, resultData);
        result.pop_back();
        check[i] = false;
    }
    
    for(int temp : resultData){
        bool result = getResult(temp);
        if(false == result ){
            answer++;
        }
    }
    
    return answer;
}

꾸준히 하다보면 실력이 늘겠지..