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

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

문제풀이

막힌 부분

1. dfs로 string을 앞뒤로 붙여가면서 숫자를 만들었다.
   -> 앞뒤로 붙여서는 모든 순열을 만들어 낼 수 없음!
2. 1의 방법에서 stoi가 안 된 이유 : 비어있는 string이 있었기 때문..

👀✨ 새롭게 알아낸 거

1. stoi 를 이용해 string->int 변환 가능! #include <string>에 있음
2. next_permutation을 이용해 순열을 만들 수 있다.

• #include <algorithm>
• 오름차순 필수!
• do,while 형태를 기억하자
  

3. 중복을 제거하기 위해 set 이용
4. 소수 판별할 때, sqrt(n) 까지만 보면 됨!

• #include <cmath>

풀이

numbers로 모든 순열을 만들어내고, 그 순열마다 앞에서 1, 2, 순열크기... 순으로 하나씩 잘라내면서 만들 수 있는 모든 수를 찾는다.
이후 isPrime()함수를 이용해서 소수인지 판별하면 됨!

코드

#include <string>
#include <cmath>
#include <algorithm>
#include <set>

using namespace std;
set<int> s;

bool isPrime(int num){

    if(num<2) return false;

    for(int i=2;i<=sqrt(num);i++){
        if(num%i==0) return false; //1말고 다른 수와 나누어 떨어지면 소수가 아님!
    }
    return true;
}


int solution(string numbers) {
    
    set<int> s;

    sort(numbers.begin(),numbers.end()); //순열 permutation을 쓰기 위핸 꼭 필요!
    do{
        for(int i=1;i<=numbers.size();i++){
            int num=stoi(numbers.substr(0,i));  //✨완성된 순열의 앞에를 순차적으로 자르기 //substr(시작인덱스, 길이)
            if(isPrime(num)) s.insert(num);
        }
    }while(next_permutation(numbers.begin(),numbers.end()));
    
    return s.size();
}