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

문제 링크 : https://programmers.co.kr/learn/courses/30/lessons/42839

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

 

문제 풀이

numbers의 최대 길이가 7이므로 모든 경우의 수를 탐색하여도 주어진 시간제한 내에 풀 수 있다.

숫자들로 이루어진 모든 수를 만들려면 조합이 필요하므로 set과 next_permutation을 사용한다.

 

"012"로 [0, 1, 2, 12, 21, 102, 120, 201, 210]와 같이 만들어야 하므로 자릿수만큼 substr하여 해당 숫자를 소수 판별한다. 소수를 판별할 때에는 에라토스테네스의 체를 사용한다. 아래는 이전에 에라토스테네스의 체에 대해 작성한 포스팅이다.

https://appdevorsec.tistory.com/57

 

소스 코드

#include <bits/stdc++.h>
using namespace std;

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

int solution(string numbers) {
    set<int> s;
    
    sort(numbers.begin(), numbers.end());
    
    int tmp = 0;
    do {
       for(int i=1; i<numbers.size() + 1; i++){
           tmp = stoi(numbers.substr(0, i));
           if(isPrime(tmp)) s.insert(tmp);
       } 
    } while(next_permutation(numbers.begin(), numbers.end()));
    
    return s.size();
}