프로그래머스 2단계 - 소수 찾기

https://programmers.co.kr/learn/courses/30/lessons/42839?language=cpp 

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

- 문제 파악

7자리 정수를 문자열로 입력된다. 이때 문자를 적절히 조합하여 소수가 되는 경우의 수를 출력하라.

 

- 정답

재귀에서 모든 경우의 수를 볼 때, 문자열 처리를 이상하게 해서 애먹었다. 생각을 제대로 하자

 

#include "bits/stdc++.h"

using namespace std;

int arr[8];
bool check[10000000];
bool ans_check[10000000];
string str;
int n;
int answer;

void func(int k, string s)
{

    if(k==n)
        return;
    
    for(int i = 0; i < n; i++)
    {
        if(!arr[i])
        {
            arr[i] = 1;
            
            s.push_back(str[i]);

            if(stoi(s) > 1 && !check[stoi(s)] && !ans_check[stoi(s)])
            {
                ans_check[stoi(s)] = true;
                answer++;
            }
                                                
            func(k+1,s);   
            s.pop_back();
            arr[i] = 0;
        }
        
        
    }
}

int solution(string numbers) {

    n = numbers.size();
    str = numbers;
    

    
    for(int i = 2 ; i*i < 10000000 ; i++)
    {
        if(check[i]) continue;
        
        for(int j = 2; i*j < 10000000 ; j++)
            check[i*j] = 1;

    }
        
    func(0,"");

    
    return answer;
}