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

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

using namespace std;

int arr[10000001] = {0}; // 7자리니까 8자리로 잡아야
vector<int> nums;
set<int> num;

// 에라토스테네스의 체
void prime(){
    arr[0] = 1; arr[1] = 1; // 0과 1은 소수 아님
    
    for(int i = 2; i < 10000001; i++){
        if(arr[i] != 0){
            continue;
        }
        
        for(int j = 2 * i; j < 10000001; j+=i){
            arr[j] = 1; // 소수 체크
        }
    }
}

int solution(string numbers) {
    int answer = 0;
    
    prime(); // 소수 체크
    
    sort(numbers.begin(), numbers.end());
    
     do{
        for(int i = 1; i <= numbers.size(); i++){
            string num = numbers.substr(0, i);
            
            if(arr[stoi(num)] == 0){
                answer++;
                arr[stoi(num)] = 3; // 방문 체크
            }
        }
    } while(next_permutation(numbers.begin(), numbers.end()));
    
    return answer;
}

인터넷 열심히 봤다...ㅋㅋ 왜냐하면 에라토스테네스의 체는 아는 알고리즘이라 생각해내기는 쉬웠는데 모든 경우에 대한 숫자를 구하는 방식이 생각이 안났기 떄문이다. DFS/BFS로 순회하면서 찾기에는 너무 불필요한 것 같았다.

• next_permutation 을 이용해서 순열 조합을 찾을 수 있다. 모든 순열 조합을 구하고, 그 조합을 잘라가면서 모든 자릿수에 대한 값을 구할 수 있다.
  (이 경우 무조건 오름차순 정리를 미리 해둬야 함)

• 11과 011을 구별하기 위해서 한 번 확인한 소수는 방문 체크를 해서 중복 체크를 하지 않도록 하였다.

• 7자리 숫자면 배열은 8자리가 필요하다... ㅋㅋ 바보