프로그래머스 - 소수 찾기

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

코딩테스트 연습 - 소수 찾기 | 프로그래머스

문자열로 주어지는 numbers의 길이가 7이하이기 때문에 완전탐색으로 풀 수 있다.

문제 카테고리도 완전 탐색이어서 바로 알 수 있긴하다...

 

1. 먼저 에라토스테네스의 체를 이용해서 소수를 모두 구해놓는다. 숫자 i가 소수라면 check[i]는 false값을 갖는다.

2. numbers의 각 자리의 값을 int형으로 변환하여 벡터에 넣어줬다.

3. 벡터에 넣어준 값들로 만들 수 있는 값들을 모두 구해서 set에 넣어준다(중복을 없애기 위해서)

4. 마지막으로 set에 있는 값들을 검사하여 소수이면 answer값을 증가시킨다.

 

 

#include <string>
#include <vector>
#include <set>
#define MAX 10000000
using namespace std;
 
bool check[MAX+1];
bool used[10];
set<int> st;
vector<int> vt;
 
void getPrime() {
    check[0] = true;
    check[1] = true;
    for(int i=2; i*i<=MAX; i++) {
        if(check[i]) continue;
        for(int j = i+i; j<=MAX; j+=i) {
            check[j] = true;
        }
    }
}
 
int n;
void select(int index, int num) {
    if(index == n) {
        //n가지 종이조각을 모두 사용하였다.
        return;
    }
    
    int newnum;
    
    //n가지의 종이조각으로 만들 수 있는 모든 수를 구한다.
    for(int i=0; i<n; i++) {
        //i번째 종이 조각을 사용하였는지 검사
        if(used[i]) continue;
        
        //i번째 종이 조각을 사용한다.
        used[i] = true;
 
        //이전의 숫자와 i번째 숫자를 합쳐준다.
        newnum = num*10+vt[i];
        
        //set에 넣고
        st.insert(newnum);
        
        //현재 만들어진 숫자에 다른 숫자를 더 붙이는 경우 탐색
        select(index+1, newnum);
 
        //다른 종이를 선택하는 경우를 위해서 다시 false값으로 변경
        used[i] = false;
    }
}
 
int solution(string numbers) {
    int answer = 0;
    n = numbers.size();
    
    //소수를 찾는다.(소수이면 check배열 값이 true)
    getPrime();
 
    
    //int로 바꿔서 vector에 넣는다.
    for(char c : numbers) {
        vt.push_back(c-'0');
    }
 
    
    //만들 수 있는 숫자 조합을 중복없이 구한다.
    select(0,0);
    
    //set에 들어가있는 값이 소수이면 answer값 증가
    for(auto iter=st.begin(); iter!=st.end(); iter++) {
        if(!check[*iter]) answer++;
    }
    
    return answer;
}