[프로그래머스] 소수찾기 (완전탐색)

오늘은 프로그래머스 완전탐색 카테고리에 있는 소수찾기 문제를 풀어보았다.

보자마자 순열, 조합으로 풀어보자는 생각을 하였고,

각 문자열을 배열이라고 생각하고

1 ~ 문자열 길이에 해당하는 조합 수를 각각 구하였다.

길이가 1인 조합 ~ 길이가 문자열길이인 조합

완전탐색을 통해 최대 길이까지 접근한 후 재귀함수를 통해서 빠져나온다.

참고로 백준온라인에 N과M이라는 문제를 풀면 도움이 될 수 있다.

#include <iostream>
#include <string>
#include <string.h>
#include <vector>
#include <algorithm>

using namespace std;

int chkBox[9999999];
vector<int> v;
bool visited[8];

int arr[8];

int answer;
void select(int idx, int M){
    if(idx == M){
        string tmps = "";
        for(int i=0;i<M;i++){
            tmps += arr[i];
        }
        int num = stoi(tmps);

        if(chkBox[num] == 0){
            int i;
            // 소수인지 확인
            for(i=2;i<num;i++){
                if(num % i == 0) break;
            }

            if(i == num) answer += 1;

            chkBox[num] = 1;
        }
        return;
    }

    for(int i=0;i<v.size(); i++){
        if(visited[i]) continue;

        visited[i] = true;
        arr[idx] = v[i];
        select(idx+1, M);
        visited[i] = false;
    }
}

int solution(string numbers) {
    answer = 0;
    memset(chkBox, 0, sizeof(chkBox));
    // 뽑아야하는 조합개수
    int cnt = numbers.length();

    // Input
    v.resize(cnt);
    for(int i=0;i<cnt;i++){
        v[i] = numbers[i];
    }

    sort(v.begin(), v.end());

    for(int i=1;i<=cnt;i++){
        memset(arr, 0, sizeof(arr));
        memset(visited, false, sizeof(visited));
        select(0, i);
    }

    return answer;
}

감사합니다.