[C++][Programmers][완전탐색] 소수찾기

[문제]

https://school.programmers.co.kr/learn/courses/30/lessons/42839?language=cpp 

프로그래머스

 

[해결법]

1) 조합으로 문자조합 뽑기

2) 1글자, 2글자, n글자씩 뽑기

3) 뽑은 수의 소수판별을 위해 문자를 int형으로 변경

4) 소수인지 판별. 소수이면 정답 개수 + 1. 이 때, 중복탐색 편리하게 하려고 unordered_set<int> answer; 변수를 만들어서 넣었다.

5) answer 사이즈 리턴

 

[알아둘 것]

1) string to int 함수

#include <cmath>
stoi("12");

2) unordered_set 자료형

#include <unordered_set>

 unordered_set<int> map; // 선언
 map.insert(1); // 삽입
 map.erase(1); // 삭제
 map[1] = 2; // 탐색 및 수정
 map.size(); // 사이즈 구하기

관련내용은 아래 포스팅 참고

https://i-believe-in-me.tistory.com/65

[C++] Hash 자료구조 / unordered_map 사용법

3) 문자열 일부 리턴

#include <string>

string str = "0123456789";

str.substr(5); // 56789
str.substr(5, 3); //567

 

[코드]

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

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

int solution(string numbers) {
    int num = 0;
    unordered_set<int> answer;
    
    //조합 돌리기 쉽게 정렬하기
    sort(numbers.begin(), numbers.end());
        
    //조합으로 수 뽑기
    do{
        for(int i = 1; i < numbers.size()+1; i++){
            //string -> int로 바꾸기
            //1글자, 2글자, n글자씩 뽑기
            num = stoi(numbers.substr(0, i));
            //뽑은 수가 소수인지 판별하기. 정답 갯수 +1
            if(isPrime(num)) answer.insert(num);
        }
    }while(next_permutation(numbers.begin(), numbers.end()));

    //소수 갯수 리턴
    return answer.size();
}