(C++) - 프로그래머스(고득점 kit - 완전탐색) : 소수 찾기

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

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

dfs를 이용한 완전탐색 문제였습니다.

 

풀이방법

 1. num.size()만큼 있는 종이 조각들을 1개부터 ~ num.size()까지 뽑아봅니다. 조합으로 뽑는게 아닌 순서가 상관있는 순열로 뽑으므로 내가 뽑았던 index를 check하기 위한 배열이 필요합니다.

 2. 정해진 개수만큼 뽑았다면 해당 수의 소수여부를 판별합니다.

    이때 뽑은 수가 이미 판별된 수라면 0을 반환합니다.

    아니라면 소수판별여부를 반환합니다.

 3. 반환된 값들을 모두 더해준 후 그 값을 반환합니다.

 

Code

#include <bits/stdc++.h>
using namespace std;
bool isPrime(int num){
    if(num <= 1) return false;
    for(int i = 2; i < num ; i++){
        if(num % i == 0) return false;
    }
    return true;
}

int dfs(int size,string num, int depth, vector<char> &c, int visitIdx[], map<int,int> &visited){
    if(depth == size){
        string tmp = "";
        for(auto s : c) tmp += s;
        int tmpNum = stoi(tmp);
        if(visited[tmpNum]) return 0;
        visited[tmpNum] = 1;
        return isPrime(tmpNum);
    }   
    
    int ans = 0;
    for(int i = 0; i < num.size(); i++){
        if(!visitIdx[i]){
            visitIdx[i] = 1;
            c.push_back(num[i]);
            ans += dfs(size,num,depth+1,c,visitIdx,visited);
            c.pop_back();
            visitIdx[i] = 0;
        }
    }   
    return ans;
}

int solution(string num) {
    vector <char> c;
    int visitIdx[100];
    map<int,int> visited;
    memset(visitIdx,0,sizeof(visitIdx));
    int ans = 0;
    for(int i = 1; i <= num.size(); i++)
        ans+=dfs(i,num,0,c,visitIdx,visited);
    return ans;
}

int main(){
    cout << solution("00011");
}