프로그래머스_소수찾기

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

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

숫자로 이루어진 문자열을 통해 만들 수 있는 소수인 특정 숫자를 만들 수 있는가를 묻는 문제였다.

풀이의 방식은 비트마스크를 통해 부분집합을 만들어온다.

그리고 만든 부분집합을 순열을 통해서 숫자로 만들고 해당 숫자가 소수인지를 확인하는 방식으로 해결하였다.

#include <string>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
bool p[10000000];

void print(int i){
    cout<<i<<"\n";
}
bool is_prime(int N) {
    if (N <= 1) return false;
    if (N == 2) return true;
    if (N == 3) return true;
    for (int i = 2; i*i <= N; i++) 
        if (N % i == 0) return false;
    return true;
}

int solution(string numbers) {
    int answer = 0;
    // 비트마스크로 해당 문자열을 쓸 것인지 뽑아온 다음 순열 돌리기
    int bound = 1 << numbers.size() ;
    for(int i=1 ; i< bound ; i++){
        string val_s = "";
        
        // bit 1개 씩 스캔
        int cnt = 0;
        for(int j=1;j<=i; j= j<<1){
            if((j & i) != 0){
                val_s.push_back(numbers[cnt]); // 숫자 값 넣기
            }
            cnt++;
        }
        string val_st = val_s;
        // 이전 순열 돌려서 소수 체크
        do{
            int val = stoi(val_st); // 숫자 변환
            
            // 검사 안했으면
            if (p[val] == 0){
                if(is_prime(val)){
                    answer++;
                }
                p[val] = 1;
            }
        }while(prev_permutation(val_st.begin(), val_st.end()));
        
        // 다음 순열 돌려서 소수 체크
        do{
            int val = stoi(val_s); // 숫자 변환
            
            // 검사 안했으면
            if (p[val] == 0){
                if(is_prime(val)){
                    answer++;
                }
                p[val] = 1;
            }
        }while(next_permutation(val_s.begin(), val_s.end()));
    }
        
    return answer;
}