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

 

소수찾기는 오랜간만인데 잘 진행해서 다행이다.

완탐 & 소수판별을 같이 진행하면 된다.

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

using namespace std;

// 1. 완탐 dfs
// 2. 소수판별

bool visit[7];
int len;
int answer;

set<int> s;

bool checkPrime(int number) {
    
    if(number <= 1) return false;
    if(number == 2) return true;
    
    for(int i = 2; i * i <= number; i++) {
        
        if(number % i == 0) {
            return false;
        }
    }
    
    return true;    
}

void dfs(string numbers, string str) {
    
    if(str.length() != 0) {
        s.insert(stoi(str));
    }
    
    
    for(int i = 0; i < len; i++) {
        
        if(!visit[i]) {
            
            visit[i] = true;
            dfs(numbers, str + numbers[i]);
            visit[i] = false;
        }
        
    }
    
}


int solution(string numbers) {
    len = numbers.length();
    
    dfs(numbers, "");
    
    for(auto x : s) {
        if(checkPrime(x)) answer++;
    }
    
    return answer;
}