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

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

코딩테스트 연습 - 소수 찾기

 

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

 

map을 꼭 쓸 필요는 없다..

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

using namespace std;

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

void dfs(int n, int sum, string numbers, vector<int> visit, unordered_map<int, int>& S) {
    if (isS(sum)) {
        if (S.find(sum) == S.end())
            S.insert({ sum,0 });
    }
    if (n == numbers.length()) {
        return;
    }

    for (int i = 0; i < numbers.length(); i++) {
        if (visit[i]) continue;
        visit[i] = 1;
        dfs(n + 1, sum * 10 + numbers[i] - '0', numbers, visit, S);
        visit[i] = 0;
    }
}

int solution(string numbers) {
    int answer = 0;

    vector<int> visit(numbers.length(), 0);
    unordered_map<int, int> S;
    dfs(0, 0, numbers, visit, S);

    return S.size();
}