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

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

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

 

풀이

• 주어진 수로 가능한 모든 조합 구하기
• 중복 값 제거하기
• 소수인지 아닌지 판단하기 (feat. 에라토스테네스의 체)

 

예시

"011"이 주어진 경우, 가능한 모든 조합은 [0, 1, 1, 10, 11, 11, 101, 110]이다.
여기서 중복을 제거하면, [0, 1, 10, 11, 101, 110]이 되고, 각 수에 대해 소수여부를 판단하면 된다.

 

next_permutation

next_permutation은 순열을 구하는 C++ 라이브러리이다. <algorithm> 헤더에 있으며, bool값을 반환한다.
자세한 사용법은 나중에 정리하고, 사용 시 주의 사항만 알아보자.

 

오름차순으로 정렬이 우선되야 한다. 오름차순으로 정렬된 값을 가진 컨테이너만 사용할 수 있다!

 

 

 

소스코드

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

vector<char> v;
vector<int> nums;

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

int solution(string numbers) {
    int answer = 0;
    int len = numbers.length();

    for(int i=0; i<len; i++)
        v.push_back(numbers[i]);

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

    //가능한 모든 조합 구하기
    for(int i=1; i<=len; i++){
	    do{
		    string cur = "";
		    for(int j=0; j<i; j++)
			    cur += v[j];
		    nums.push_back(stoi(cur));
	    } while(next_permutation(v.begin(), v.end()));
    }

    //중복 제거
    sort(nums.begin(), nums.end());
    nums.erase(unique(nums.begin(), nums.end()), nums.end());

    for(unsigned int i=0; i<nums.size(); i++){
    	if(isPrimeNum(nums[i])) answer++;
     }
    
    return answer;
}