[C++] level2 소수 찾기 42839

📌소수 찾기

/* 해당 문제 설명은 링크로 대체한다. */

📌풀이

이 문제는 주어진 문자열에서 조각 조각으로 나눠서 소수를 찾아내는 문제이다.
이것은 next_permutation() 을 이용해야 함을 알 수 있다.
왜냐, 입출력 예시도 있지만 17이 주어질 때 7, 17, 71 이런 식으로 숫자로 구할 수 있는 경우의 수 중 소수를 골라서 count를 증가시켜줘야하기 때문이다.

그래서 나는 isPrime()를 통해서 소수를 먼저 찾았고,
do-while()을 돌면서 해당 순열에서 숫자를 substr()로 뽑아내 소수라면 set에 담아두었다.
set을 사용한 이유는 순열에 따라 만들어지는 소수가 이미 만들었다면 또 중복해서 담지 않기 위함
그리고 set의 size()를 반환하였다.

📌코드

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

bool isPrime(int n)
{
    //1보다 크면서 1과 자기자신만 약수를 갖는 수 == 소수
    if (n == 1 || n == 0)
        return false;
    if (n == 2)
        return true;

    for (int i = 2; i <= sqrt(n); i++)
    {
        if (n % i == 0) //소수가 아님
            return false;
    }
    return true;
}

int solution(string numbers)
{
    set<int> ans;                         //만들 수 있는 소수
    sort(numbers.begin(), numbers.end()); //오름차순으로 정렬

    //numbers를 돌며 순열을 생성하여 소수 확인
    do
    {
        for (int i = 1; i <= numbers.size(); i++)
        {
            string temp = numbers.substr(0, i);

            if (isPrime(stoi(temp)))
                ans.insert(stoi(temp));
        }
    } while (next_permutation(numbers.begin(), numbers.end()));

    return ans.size();
}

---

회고
전에 작성했던 코드랑 비교했을 대 크게 달라진 점은 없었지만, 이번 코드가 더 깔끔해졌다!
아주 조오그음 성장했다 ..... ㅋㅋ .....