[프로그래머스] 소수 찾기Level 2

문제

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

프로그래머스

핵심

1. 완전 탐색 알고리즘 기법 중 하나인 bitmask 기법을  알아야한다. 

2. 순열을 구하는 알고리즘을 알아야한다.

    - C++에는 순열을 구하는 next_permutation 함수가 존재한다.

4. 소수 판별 법을 알아야 한다.

3. 문자열 연산은 느리다. 숫자 연산을 최대한 한다.

 

코드

#include <string>
#include <vector>
#include <iostream>
#include <cmath>
#include <algorithm>
#include <sstream>
#include <set>

using namespace std;

bool sosu(int num){
    if(num==1||num==0)
        return false;

    for(int i=2; i*i<=num;i++){
        if(num%i==0){
            return false;
        }
    }
    return true;
}

int solution(string numbers) {
    int answer = 0;
    std::vector<char> v;
    std::vector<int> p;
    std::set<int> ans;
    
    // 1단계 쪼개라. 
    for (int i = 0; i < numbers.length(); i++) {
        v.push_back(numbers[i]);
    }
    
    int size = v.size();
    for (int i = 0; i < (1 << size); i++) {
        for (int j = 0; j < size; j++) {
            if (i & (1 << j)) {
                p.push_back(v[j]-'0');
            }
        } 
        
        std::sort(p.begin(), p.end(), std::less<int>());
        do {
            
            int n = p.size() -1, value = 0;
            for (auto i : p) {
                value += i * (pow(10, n--));
            }
            
            //std::cout << value << std::endl;
            if (true == sosu(value)) {
                ans.insert(value);    
            }
        } while (next_permutation(p.begin(), p.end()));    
        p.clear();
    }
    
    answer = ans.size();
    return answer ;
}