[C++/PGS] Lv.2 : 소수 찾기 (완전탐색)

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

 

문제 설명

한자리 숫자가 적힌 종이 조각이 흩어져있습니다. 흩어진 종이 조각을 붙여 소수를 몇 개 만들 수 있는지 알아내려 합니다.

각 종이 조각에 적힌 숫자가 적힌 문자열 numbers가 주어졌을 때, 종이 조각으로 만들 수 있는 소수가 몇 개인지 return 하도록 solution 함수를 완성해주세요.

 

제한사항

• numbers는 길이 1 이상 7 이하인 문자열입니다.
• numbers는 0~9까지 숫자만으로 이루어져 있습니다.
• "013"은 0, 1, 3 숫자가 적힌 종이 조각이 흩어져있다는 의미입니다.

---

 

1. set 은 중복을 걸러주는 집합이다!

 

2. 소수를 확인할 때에는 숫자를 나누는 반복문의 범위를 2 이상 sqrt(n) 이하로 설정한다

 

3. algorithm 헤더파일의 next_permutation 함수를 사용하면, 모든 순열을 하나씩 구할 수 있다.

-> 대신, 모든 경우의 수를 올바르게 구하기 위해서는 먼저 정렬이 필요함

 

4.. while()~ 대신 do while 문을 사용하는 이유는?

-> next_permutation을 이용하여 다음 순열로 넘어가기 전에, 처음 상태의 순열로도 do 내부의 내용을 실행시켜야 하기 때문.

 

 

나의 풀이

#include <string>
#include <vector>
#include <algorithm>
#include <set>
#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;
    int n=0;
    set<int> s;
    sort(numbers.begin(), numbers.end());
    do{
        for(int i=0; i<numbers.length(); ++i){
            n = stoi(numbers.substr(0,i+1));
            if(isPrime(n)) s.insert(n);
        }
    } while(next_permutation(numbers.begin(), numbers.end()));
    answer = s.size();
    return answer;
}