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

 

알고리즘

생각한 알고리즘을 다음 세가지 단계로 나눴다.

1. 받은 종이조각의 숫자들을 하나하나 배열에 넣어서, 만들 수 있는 모든 숫자 조합을 구하기(next_permutation사용).

2. 011과 11이 같은 숫자인 것처럼, 중복을 제거하기

3. 에라토스테네스의 체를 이용해서 소수판별하기

 

정리

만들 수 있는 숫자 조합을 모두 구하는 과정에서 가령 1,2,0의 숫자가 있을 경우에 순열(next_permutation)로 120, 102, 210, 201, 012, 021의 숫자를 만든 후에, 각자의 숫자에 대해서 숫자를 하나씩 더해가면서 (120의 경우 1, 12, 120 세개의 수를 만들 수 있다.) 모든 숫자조합을 만들 수 있었다.

STL이 지원하는 vector의 기능들에 대해서 잘 사용해볼 수 있었던 문제이다. 중복을 제거할 때 사용되는 v.erase(unique(v.begin(),v.end()),v.end())같은 메서드는 이전 글에 정리를 해놨지만 외우면 굉장히 편리한 도구임을 느꼈다. 그리고 string에도 push_back()이 된다는 걸 처음알았다...

소수판별을 위한 알고리즘인 에라토스테네스의 체 같은 경우도 다시 한번 복습할 수 있었다. 

https://blog.naver.com/PostView.naver?blogId=ndb796&logNo=221233595886&redirect=Dlog&widgetTypeCall=true&directAccess=false 

22. 에라토스테네스의 체

 

 

Code

#include <string>
#include <vector>
#include <iostream>
#include <algorithm>
#include <cmath>
 
using namespace std;
 
//에라토스테네스의 체
bool isPrime(int n){
    if(n<2)
        return false;
    
    for(int i=2;i<=sqrt(n);i++){
        if(n%i==0)
            return false;
    }
    
    return true;
}
 
int solution(string numbers) {
    int answer = 0;
    vector<char> v;
    vector<int> num;
    
    for(int i=0;i<numbers.size();i++){
        v.push_back(numbers[i]);
    }
    
    //모든 숫자조합 구하기
    sort(v.begin(),v.end());
    do{
        string tmp = "";
        for(int i=0;i<v.size();i++){
            tmp.push_back(v[i]);
            num.push_back(stoi(tmp));
        }
    }while(next_permutation(v.begin(),v.end()));
    
    //중복 제거
    sort(num.begin(),num.end());    
    num.erase(unique(num.begin(),num.end()),num.end());
 
    //소수 판별
    for(int i=0;i<num.size();i++){
        if(isPrime(num[i])){
            answer++;
        }
    }
 
    return answer;
}