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

Memo

로직 설명

• 문자열로 만들 수 있는 숫자를 모두 만든 후, 소수를 판별 합니다.

Code

제출 날짜

2021/05/07

#include <string>
#include <vector>

bool visited[8];
bool check[10000000];
int answer;

void brute(int val, int depth, int& max_depth, int& n_size, std::string& numbers)
{
	if (max_depth == depth)
	{
		int i = 2;

		if (val <= 1 || check[val])
			return;
		while (val > i)
		{
			if (!(val % i))
				return ;
			i++;
		}
		check[val] = 1;
		answer++;
		return ;
	}
	for (int i = 0 ; i < n_size ; i++)
	{
		if (visited[i])
			continue;
		visited[i] = 1;
		brute(val * 10 + (numbers[i] - '0'), depth + 1, max_depth, n_size, numbers);
		visited[i] = 0;
	}
}

int solution(std::string numbers) {
    int n_size = numbers.size();

    for (int i = 1 ; i <= n_size ; i++)
	    brute(0, 0, i, n_size, numbers);
    return answer;
}