🖊️ 문제

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

---

🖊️ 풀이

진짜 .. 욕나왔다
ㅠㅠ
완전탐색 이라는데 ..
문제 이해를 잘못해가지고 ..... ㅜㅜ

일단 전체적으로,,
숫자 조각들의 조합을 구하는게 대박 오래걸렸다..

소수판별이야 뭐 에라토스테네스의 체로 구하면 되니까 쉬웠는데 ..

일단 !!

next_permutation

<algorithm> 헤더 필요
전달받은 iterator의 범위 내에 있는 원소들을 다음 경우의 수 로 바꿔준다.
사용 전에 정렬 필요함 (정렬되기 이전의 경우의 수는 보장 X)

#include <string>
#include <vector>
#include <iostream>
#include <algorithm>

using namespace std;

int solution(string numbers) {
    int answer = 0;
    vector<int> subset;
    
    // 숫자들의 전체 조합 찾기
    sort(numbers.begin(), numbers.end());
    
    do {
       for(int i = 1 ; i<= numbers.size() ; i++) {
           string num = numbers.substr(0, i);
           subset.emplace_back(atoi(num.c_str()));
       }
    } while(next_permutation(numbers.begin(), numbers.end()));
    
    sort(subset.begin(), subset.end());
    subset.erase(unique(subset.begin(), subset.end()), subset.end());
    
    // vec에서 소수 찾기
    
    vector<bool> check;
    for(int i = 0 ; i <= subset[subset.size()-1] ; i++)
        check.emplace_back(false);
    
    check[0] = true;
    check[1] = true;
    
    for(int i = 2 ; i <= subset[subset.size()-1] ; i++) {
        if (check[i]) continue;
        for(int j = 2 * i ; j <= subset[subset.size()-1] ; j += i)
            check[j] = true;
	}
    
    for(auto& v : subset) {
        if (!check[v]) 
           	answer++;
    }
    
    return answer;
}

난
정말
내가
싫 다 ..

---

참고
https://en.cppreference.com/w/cpp/algorithm/next_permutation
https://twpower.github.io/82-next_permutation-and-prev_permutation
https://togomi.tistory.com/67