[프로그래머스/알고리즘] 소수 찾기

문제 설명 

한자리 숫자가 적힌 종이 조각이 흩어져있습니다.

흩어진 종이 조각을 붙여 소수를 몇 개 만들 수 있는지 알아내려 합니다.

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

해결 방법

문자열 변수인 string은 sort함수를 사용할 수 있습니다.

내림차순을 이용하면 number는 가장 큰 수를 만들어 낼 수 있습니다.

예로들면 "17"은 71로 변하기 떄문에 2~71까지 비교해서 해당 조각에 만족하는 소수를 찾아내면 됩니다.

number는 기본적으로 문자열로 되어있기 때문에 정수로 변하려면 stoi함수를 이용했고

71을 구했으면 2~71까지 비교하는데 7이나 1을 사용했는지 안했는지 확인하는 visit 배열을 이용해서 계산 했습니다.

소스 코드

#include <string>
#include <vector>
#include <algorithm>
#include <functional>
using namespace std;
bool checkNumber(int i, string numbers);
int solution(string numbers) {
	int answer = 0;
	sort(numbers.begin(), numbers.end(), greater<int>());
	vector<bool> temp(stoi(numbers)+1);
	for (int i = 2; i <= stoi(numbers); i++) {
		if (temp[i]==false && checkNumber(i,numbers)) {
			answer++;
		}
		if (temp[i] == false) {
			for (int j = i; j <= stoi(numbers); j += i) {
				temp[j] = true;
			}
		}
	}
	
	return answer;
}

bool checkNumber(int i,string numbers) {
	bool flag = false;
	vector<bool> visit(numbers.length());
	while (i != 0) {
		flag = false;
		int temp = i % 10;
		for (int j = 0; j <= numbers.length(); j++) {
			if (temp == numbers[j]-'0'&&visit[j]==0) {
				flag = true;
				visit[j] = 1;
				break;
			}
		}
		if (flag == false)
			return false;

		i /= 10;
	}

	return true;
}