[완전탐색, 난이도 중] 프로그래머즈, 소수 찾기

종이 조각을 조합할 수 있는 모든 경우의 수를 탐색해야 하는 브루트포스 문제이다.

 

prime_check 함수는 소수 여부를 판단하는 함수이다.

각 자릿수는 0~9로 이루어져 있으니 문자열 numbers를 문자 단위로 쪼개서 arr 벡터에 넣고 계산을 수행했다.

순열을 이용하여 arr 벡터의 요소들을 조합하여 자료형만 문자열인 정수를 만들어낸뒤, stoi 함수를 이용하여 자료형을 string에서 int로 변환해주었다.

 

permutation이 순열 함수이고 매개변수는 (총 요소의 수, 고를 요소의 수, 재귀함수 깊이) 이다.

순열 알고리즘에 대해 다룬 포스팅 링크이다.

kimcoder.tistory.com/115

재귀를 이용한 간단한 순열 알고리즘

 

numbers의 길이가 n 이라면 numbers에서 1개~n개의 수를 고르는 경우를 모두 고려해주었다.

자릿수가 겹치는 경우도 존재하므로 erase, unique 함수를 이용하여 벡터의 중복 요소도 제거해 주었다.

erase, unique 함수에 대해 다룬 포스팅 링크이니 참고하면 도움이 될 것이다.

kimcoder.tistory.com/100?category=887790

벡터 정렬 후, 중복 요소 제거하기

 

테스트 케이스 12개 모두 통과

 

#include <vector>
#include <string>
#include <math.h>
#include <algorithm>
using namespace std;

vector<int> arr;
vector<int> ans;
void swap(int *a, int *b ){
	int tmp;
	tmp = *a;
	*a = *b;
	*b = tmp;
}

void prime_check(int size){
	string prime_s ="";
	for(int i=0; i < size; i++){
            prime_s += (arr[i]+'0');
	}
	int prime = stoi(prime_s);
	if(prime==0||prime==1) return;
	for(int i=2;i<=sqrt(prime);i++){
            if(prime%i==0) return;
	}
	ans.push_back(prime);		
}

void permutation(int n, int r, int depth){
	if(r == depth){
	    prime_check(depth);
	    return;
	}
	for(int i=depth; i<n; i++){
	    swap(&arr[i], &arr[depth]);
	    permutation(n, r, depth+1);
	    swap(&arr[i], &arr[depth]);
	}
}

int solution(string numbers) {
    int answer;
    int ns = numbers.length();
    for(int i=0;i<ns;i++)   arr.push_back(numbers[i]-'0');
    for(int i=1;i<=ns;i++)  permutation(ns,i,0);
    
    //중복요소 제거
    sort(ans.begin(),ans.end());
    ans.erase(unique(ans.begin(),ans.end()),ans.end());
    
    answer = ans.size();
    return answer;
}