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

(6/20 - △)

 

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

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

 

 

구현

두 가지를 고민해야 한다.

1. 숫자들의 조합을 빠짐없이 구해서 저장하기.

 - 예를 들어 "013"일 경우, next_permutation으로 조합을 만들면 {013}, {031}, {310}, {301}만 구할 수 있고 {0}, {1}, {3}, {01} 등의 경우가 누락된다. -> 재귀를 이용한 next_permutation. 아래 코드 참고!

 - 중복되지 않게 담으려면 어디에 담을 것인가 -> set

2. 소수인지 판별하기.

 - n이 소수인지 판별한다면, n에다 2부터 n까지의 수를 나누어서 나머지가 0이 나온 경우가 있다면 소수가 아님으로 판정.

 

실수한 부분

next_permutation으로 조합을 구할 때 오름차순으로 정렬한 후 해야 한다. 이거 때문에 세모 표시 했다.

 

 

 

코드

#include <string>
#include <vector>
#include <set>
#include <algorithm>


using namespace std;

set<int> s;

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

void recurs(vector<int>& v, int size, int cnt, string& st) {
    if (cnt >= size) return;
    st.push_back(v[cnt++]);
    s.insert(stoi(st));
    recurs(v, size, cnt, st);
}

int solution(string numbers) {
    int answer = 0;
    int len = numbers.length();
    vector<int> v(len);
    for (int i = 0; i < len; i++) {
        v[i] = numbers[i];
    }

    sort(v.begin(), v.end());

    do {
        string st = "";
        recurs(v, len, 0, st); // 0
    } while (next_permutation(v.begin(), v.end()));
    
    set<int>::iterator i_b = s.begin();
    set<int>::iterator i_e = s.end();

    for (; i_b != i_e; i_b++) {
        if (isPrime((*i_b))) answer++;
    }

    return answer;
}