[프로그래머스/Lv2] 소수 찾기

 

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

프로그래머스

 

 

에라토스테네스의 체를 사용해서 소수를 빠르게 찾아볼까 했는데

그냥 하나씩 소수인지 체크해봐도 충분히 돌아간다.

자릿수 개수만큼 백트래킹을 사용해서 돌려서 수를 찾은 뒤에 소수인지 판별하고 set에 넣어서 중복을 제거해줬다.

last는 마지막으로 사용한 원소가 무엇인지 저장해주는 것인데, 이를 통해서 "011"과 같은 수에서 BT를 통해

1이 두 개여서 발생할 수 있는 문제 → 01, 01 두 번 나오기! (앞의 1과 뒤의 1은 다름)를 없애준다.

 

 

#include <algorithm>
#include <cmath>
#include <cstring>
#include <set>
using namespace std;
bool visit[10];
int ans = 0;
set<int> ss;

bool isPrime(int x){
    if(x==0||x==1) return false;
    for(int i=2; i<x; i++){
        if(x%i == 0) return false;
    }
    return true;
}

void BT(int cnt, int k, string s, string numbers){
    if(cnt == k){           //k개의 숫자를 모았으면 소수인지 체크
        int n = stoi(s);
        if(isPrime(n)) ss.insert(n); //중복 제거
        return;
    }
    
    int last = 0;
    for(int i=0; i<numbers.size(); i++){
        if(!visit[i] && last != numbers[i]){
            last = numbers[i];
            visit[i] = true;
            BT(cnt+1, k, s+numbers[i], numbers);
            visit[i] = false;
        }
    }
}

int solution(string numbers) {
    int answer = 0;
    for(int i=1; i<=numbers.size(); i++){
        memset(visit, false, 10); //초기화
        BT(0, i, "", numbers);    //자릿수 개수(i)
    }
    answer = ss.size();
    return answer;
}