[프로그래머스] 소수찾기 | c++

완탐인데 조건따져보며 경우의 수 따져봐야함

& 인덱스 중복X(배열자체에 같은 수가 들어오는건 따로 처리해줘야함), 수열만들기

-> 1. 백트래킹 & 재귀 이용 

#include <string>
#include <vector>
#include <algorithm>
#include <cmath>
#include<iostream>
using namespace std;

int arr[8]; //기본 배열
int mine[8]; //모인 카드 저장할거임
int check[8]; //들어간 수인지 확인
int isExist[7777777]; //같은 숫자 대칭 처리 
//ex."011"이 주어졌을때 나오는 101과 같은 조합은 1이 2번주어져있어서 각각의 1이 다른 값으로 처리됨. -> 중복카운트발생
//이를 방지하기 위해 한번 처리한 소수를 인덱스로 표현하여 저장

int n;
int answer;
void func(int depth, int targetSize){ //현재 모인 카드개수, 몇 자리수 소수 찾는지
    
    if(depth == targetSize){
        if(targetSize==1 && mine[0] <2) return;
        if(mine[targetSize-1] == 0) return; //1-인덱스부터 1의 자리
        int curNum =0;
        for(int i =0;i<targetSize;i++){
            curNum += mine[i]*pow(10,i);
        }
        int d = static_cast<int>(round(sqrt(curNum)));
    
        for(int i =2; i<=d; i++){
            if(curNum%i ==0) return; //소수가 아님
        }
        if(!isExist[curNum]){//대칭수에 걸리나 확인
            cout <<curNum<<'\n';
            answer++;//소수임  
            isExist[curNum]=true;
        } 
        return;  
    }
    for(int i =0;i<n;i++){
        if(!check[i]){
            check[i] =true;
            mine[depth] = arr[i];
            func(depth+1,targetSize);
            check[i]=false;
        }
        
    }
    
}

int solution(string numbers) {
    //숫자 조합 , 같은 숫자 여러개일수도 
    //순열,인덱스 중복 X -> 재귀 
    //몇개를 고르는가? -> 1개~ 숫자카드 개수 개 -> func 여러번 호출?
    
    n = numbers.length(); // 숫자카드 개수
    
    for(int i =0;i<n;i++){
        // arr[i] = stoi(numbers[i]);
        arr[i] = numbers[i]-'0';
    }
    
    sort(arr,arr+n);

    for(int i =1;i<n+1;i++){
        func(0,i);
    }
    
    
    return answer;
}

 

 

-> 2. next_permutation 이용

#include <string>
#include <vector>
#include <algorithm>
#include<iostream>
#include<cmath>
using namespace std;

vector<char> arr;
vector<string> mine;
int answer;
int isExist[9999999];

bool isN(int d, int cur){
    for(int j=2;j<=d;j++){
        if(cur%j == 0){//소수아님
            return false;
        }
    }
    return true;
}
void func(){
    for(int i =0;i<mine.size();i++){
        string c = mine[i];
        if(c[0]==0)continue;
    
        int cur = stoi(c);
        if(cur<2) continue;
        
        int d = static_cast<int>(round(sqrt(cur)));
        
        if(isN(d,cur)){
            if(isExist[cur]==0){
                isExist[cur]=1;
                answer++;
            }
        }
        
    }
}
int solution(string numbers) {
    
    for(int i =0;i<numbers.length();i++){
        arr.push_back(numbers[i]);
    }
    
    sort(arr.begin(),arr.end());
    
    for(int i =1;i<=numbers.length();i++){
        do{
            string curN ="";
            for(int j =0;j<i;j++){
                curN += arr[j];
            }
            mine.push_back(curN);
            reverse(arr.begin()+i,arr.end());

        }while(next_permutation(arr.begin(),arr.end()));
        
        func();
    }
    
    
    return answer;
}