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

문제 : 소수 찾기

---

풀이 방법

조합과 순열을 적절히 섞어야하며 자릿수도 신경 써야하므로 for문 안에 do while (next_permutation)을 넣었다.

프로그래머스 소수 찾기 11번 케이스만 오답이 나서 뭔가 했는데 numbers를 sort하지 않아서 오류가 났던 것이다.

경우의 수를 전부 체크하고 나면 01과 1은 같은 숫자로 치므로 0도 제거 한 다음, 중복되는 숫자를 제거해서 소수를 체크하면 끝이다

---

소스 코드

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

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

int solution(string numbers) {
    int answer = 0;
    vector<string> vecNumbers;
    
    // numbers를 오름차순으로 정렬 next_permutation은 정렬되어 있어야함
    sort(numbers.begin(), numbers.end());
    
    // 자릿수 별로 조합
    for(int i=1; i<=numbers.length(); i++) {
        do {
            string tmp = "";
            
            for(int u=0; u<i; u++) {
                tmp.push_back(numbers[u]);
            }
            
            // 011의 0은 필요없으니 맨 앞의 0 제거
            while(tmp.front() == '0') tmp.erase(tmp.begin());
            if(!tmp.empty()) vecNumbers.push_back(tmp);
            
        } while (next_permutation(numbers.begin(), numbers.end()));
    }
    
    // 중복되는 숫자 제거
    sort(vecNumbers.begin(), vecNumbers.end());
    vecNumbers.erase(unique(vecNumbers.begin(), vecNumbers.end()), vecNumbers.end());
    
    // 소수 개수 체크
    for(string s : vecNumbers) {
        int i = stoi(s);
        if(isPrime(i) == true) answer++;
    }
    
    return answer;
}