[2023년 11월 23일]소수 찾기(21분)

https://school.programmers.co.kr/learn/courses/30/lessons/42839

구현 아이디어 1분 구현 20분

풀이

#include <string>
#include <vector>
#include <map>

using namespace std;

// 종이 조각으로 만들 수 있는 숫자 조합 만들기.
// 소수 판별.
// 011과 11은 같은 숫자기 때문에 중복 검사 하지 않도록 넘어가야 함.
int N, answer, check[7];
char comb[7];
map<int, int> dup;

void DFS(int L, int e, const string& numbers)
{
    if(L == e)
    {
        // 소수 판별.
        string tmp;
        for(int i = 0; i < e; ++i)
            tmp += comb[i];
        
        int num = stoi(tmp);
        if(num <= 1) return;
        if(dup[num]) return;
        ++dup[num];
        
        for(int i = 2; i * i <= num; ++i)
            if(num % i == 0) return;
        
        ++answer;
    }
    else
    {
        for(int i = 0; i < numbers.size(); ++i)
        {
            if(check[i] == 0)
            {
                check[i] = 1;
                comb[L] = numbers[i];
                DFS(L + 1, e, numbers);
                check[i] = 0;
            }
        }
    }
}

int solution(string numbers) {
    N = numbers.size();
    for(int i = 1; i <= N; ++i)
        DFS(0, i, numbers);
    
    return answer;
}