[프로그래머스 / Level_2] 소수 찾기

완전 탐색 문제이다. 

 

#접근방법 

카드 번호로 만들 수 있는 모든 값들을 조합해보면서 소수를 찾는 문제이다. 

 

dfs를 처음 호출했을 때는 만들어진 문자열이 없으므로 

level이 1 이상일 때만 현재 만들어진 문자열이 소수인지 체크한다. 

 

문자열로 전달하였기 때문에 stoi 함수를 활용해서 int형으로 변환 후 prime_check 함수를 호출하여 

해당 값이 소수인지 판별한다. 

 

만약 그 값이 소수라면 set 자료구조를 이용해서 해당 값을 넣어준다. ( set은 중복 무시 ) 

이후 방문처리 되지 않은 카드가 있다면 문자열 뒤에 붙여주면서 dfs를 호출한다. 

 

dfs 호출 후 돌아오고 나면 다른 case에서도 사용해야하기 때문에 방문 처리했던 값을 다시 false로 반환한다. 

#include <string>
#include <vector>
#include <iostream>
#include <set>
using namespace std; 
vector <char> v; 
vector <bool> check; 
set <int> se; 
bool prime_check(int x){
    if(x==0||x==1)return false; 
    for(int i=2; i<x; i++) if(x%i==0) return false;         
    return true; 
}

void dfs(int level, string s){   
    if(level>=1){
        if(prime_check(stoi(s))) se.insert(stoi(s)); 
    }
    for(int i=0; i<v.size(); i++){
        if(check[i]==true)continue; 
        check[i]=true; 
        dfs(level+1, s+v[i]); 
        check[i]=false; 
    }   
}
int solution(string numbers) {
    for(int i=0; i<numbers.size(); i++) v.push_back(numbers[i]);            
    check.resize(v.size(),false); 
    dfs(0, "");    
    return se.size();
}

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