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

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

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

 

1. 문자열의 각 요소를 정수로 바꾸어 벡터에 넣어준다.

2. 정렬을 한 후, next_permutation을 이용하여 벡터의 순열을 구한다.

  (num = num * 10 + v[i] 식을 통해 한자리부터 n자리 까지의 수를 구할 수 있다.)

3. 순열을 통해 만들어지는 수를 set에 저장한다. (중복을 없애기 위해 set을 사용)

4. set의 iterator를 선언하고, 소수를 판별하는 함수인 isPrime() 에 넣어 비교해본다.

 

#include <string>
#include <vector>
#include <set>
#include <algorithm>
using namespace std;

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

int solution(string numbers) {
    int res = 0;
    vector<int> v;
    set<int> s;
    
    for(int i = 0; i < numbers.size();i++) {
        v.push_back(numbers[i]-'0');
    }
    sort(v.begin(), v.end());
    
    
    do {
        int num = 0;
        for(int i = 0; i < v.size(); i++) {
            num = num * 10 + v[i];
            s.insert(num);
        }
    } while(next_permutation(v.begin(), v.end()));
    
    set<int>::iterator it;
    for(it = s.begin(); it != s.end(); it++) {
        if(isPrime(*it)) res++;
    }
    
    return res;
}

 

// DFS를 이용한 순열 구하기

#include <string>
#include <vector>
#include <set>
using namespace std;

string Numbers;
int res[8];
bool visit[8];
set<int> s;

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

void DFS(int cnt, int size) {
    if(cnt == size) {
        int sum = 0;
        for(int i = 0; i < size; i++) {
            sum = sum * 10 + res[i];
        }
        if(isPrime(sum)) s.insert(sum); // "01", "1" 은 같게 봐야하므로
        return;
    } else {
        for(int i = 0; i < Numbers.size(); i++) {
            if(!visit[i]) {
                visit[i] = true;
                res[cnt] = Numbers[i] - '0';
                DFS(cnt + 1, size);
                visit[i] = false;
            }
        }
    }
}

int solution(string numbers) {
    Numbers = numbers;
    for(int i = 1; i <= numbers.size(); i++) {
        DFS(0, i);    
    }
    
    return s.size();
}

 

#include <string>
#include <vector>
#include <set>
using namespace std;

string Numbers;
set<int> st;
bool visit[8];

bool isPossible(int num) {
    if(num < 2) return false;
    if(num == 2) return true;
    for(int i = 2; i * i <= num; i++) {
        if(num % i == 0) return false;
    }
    return true;
}

void DFS(int cnt, int size, string path) {
    if(cnt == size) {
        int num = stoi(path);
        if(isPossible(num)) st.insert(num);
        return;
    }
    
    for(int i = 0; i < Numbers.size(); i++) {
        if(!visit[i]) {
            visit[i] = true;
            DFS(cnt + 1, size, path + Numbers[i]);
            visit[i] = false;
        }
    }
}

int solution(string numbers) {
    Numbers = numbers;
    for(int i = 1; i <= numbers.size(); i++) {
        DFS(0, i, "");
    }
    return st.size();
}