[프로그래머스 C++] - 소수 찾기

문제 : 소수 찾기

문제 설명

 한자리 숫자가 적힌 종이 조각이 흩어져있습니다. 흩어진 종이 조각을 붙여 소수를 몇 개 만들 수 있는지 알아내려 합니다.

각 종이 조각에 적힌 숫자가 적힌 문자열 numbers가 주어졌을 때, 종이 조각으로 만들 수 있는 소수가 몇 개인지 return 하도록 solution 함수를 완성해주세요.

 

제한사항

• numbers는 길이 1 이상 7 이하인 문자열입니다.
• numbers는 0~9까지 숫자만으로 이루어져 있습니다.
• 013은 0, 1, 3 숫자가 적힌 종이 조각이 흩어져있다는 의미입니다.

 분석

 숫자가 소수인지 판단하는 것과 숫자를 조합하는 하는 것이 이 문제의 포인트이다. 소수인지 판단하는 건 에라토스테네스의 체를 이용하면 된다. 숫자를 조합하는 과정은 일단 조합으로 처리한 뒤 중복되는 수를 제거하면 된다.

 

 구현

// 에라토스테네스의 체
// 주어진 숫자가 소수인지를 판단
bool is_primenum(int n)
{
	if (n <= 1) return false;

	int k = (int)sqrt(n);
	for (size_t i = 2; i <= k; i++)
	{
		if (n%i == 0) return false;
	}
	return true;
}

vector<int> arr;
vector<bool> selected;
vector<int> tmp_num, real_num;

// 조합 수를 중복되지 않게 저장
// r은 자릿수
void make_num(int r)
{
	int n = 0;

	for (size_t i = 0; i < tmp_num.size(); i++)
	{
		n += pow(10, (r - 1))*tmp_num[i];
		r--;
	}

	// 조합수 생성 후 중복된 수인지 판단
	if (real_num.empty()) real_num.push_back(n);
	else
	{
		for (size_t i = 0; i < real_num.size(); i++)
		{
			if (n == real_num[i]) return;
		}
		real_num.push_back(n);
	}
}

// 조합
void DFS(int cnt, int r)
{
	if (cnt == r)
	{
		make_num(r);
		return;
	}

	for (size_t i = 0; i < arr.size(); i++)
	{
		if (selected[i] == true) continue;
		selected[i] = true;
		tmp_num.push_back(arr[i]);
		DFS(cnt + 1, r);
		tmp_num.pop_back();
		selected[i] = false;
	}
}

int solution(string numbers)
{
	int answer = 0;
	
	// 데이터 타입 변환
	for (size_t i = 0; i < numbers.size(); i++)
	{
		int tmp = numbers[i] - '0';
		arr.push_back(tmp);
		selected.push_back(0);
	}

	// 조합 생성 
	for (size_t i = 1; i <= arr.size(); i++)
	{
		DFS(0, i);
	}

	// 겹치는 수 제외 후 소수인지 판단
	for (size_t i = 0; i < real_num.size(); i++)
	{
		if (is_primenum(real_num[i]))
		{
			answer++;
		}
	}

	return answer;
}

int main()
{
	int a = solution("011");
	cout << a << '\n';
	return 0;
}