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

문제 설명

---

제한 사항 및 입출력 예제

---

개념

　이 문제는 주어진 문자열에서 추출 가능한 모든 숫자 조합 중 소수가 몇 개 있는지를 찾는 문제다. 이 문제를 해결하기 위해서는 두 가지 주요 과정이 필요하다.

 

　먼저 가능한 모든 숫자 조합을 생성해야 한다는 것이다. 이 과정에서 문자열의 순열을 찾는 개념을 사용한다. 즉, 주어진 문자열의 모든 문자를 사용하여 만들 수 있는 모든 숫자 조합을 배열에 담는다. 두 번째는 소수를 판별하는 것이다. 생성된 모든 숫자 조합을 순회하며 소수인지 판별한다.

 

　문제를 해결하는 과정에서 주의해야 할 점은 동일한 숫자가 두 번 이상 카운트되면 안 된다는 점이다. 예를 들어 "11"은 "1"이 두 번 등장하므로 소수인 11이 두 번 카운트되어서는 안 된다. 이 문제는 중복을 허용하지 않는 자료구조를 사용함으로써 해결할 수 있다.

---

풀이

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

bool isPrime(int num)
{
    if (num <= 1)
        return false;

    if (num == 2 || num == 3)
        return true;

    if (num % 2 == 0 || num % 3 == 0)
        return false;

    for (int i = 5; i * i <= num; i += 6)
    {
        if (num % i == 0 || num % (i + 2) == 0)
            return false;
    }

    return true;
}

　소수를 판별하는 함수 isPrime()이다. 이때 소수의 검사 범위를 제곱근까지만 검사하게 하여 효율성을 증대시켰다.

int solution(string numbers) 
{
    set<int> ans;
    int answer = 0;
    int n = numbers.size();

    for (int i = 1; i < (1 << n); ++i)
    {
        string tmp = "";

        for (int j = 0; j < n; ++j)
        {
            if ((i & (1 << j)) != 0)
                tmp += numbers[j];
        }

　숫자의 조합들을 저장할 집합 ans를 초기화한다. 우리가 확인해야 할 가짓수는 2^n개이므로, 반복 범위를 i << n으로 설정한다(이진수 표현에서 i << n는 2^n을 의미). 따라서 i는 1부터 2^n - 1까지의 값을 가진다.

　그리고 현재 i에 대해 선택된 문자들로부터 부분 문자열을 생성한다. i << j는 j번 째 비트를 설정하고, i & (1 << j)는 i의 j번째 비트가 1인지 확인한다. 만약 i의 j번째 비트가 1이면 j번째 문자가 현재 부분 문자열에 포함되어야 한다는 뜻이므로 tmp에 문자를 추가한다.

 

        sort(tmp.begin(), tmp.end());

        do
        {
            if (tmp[0] == '0')
                continue;

            ans.insert(stoi(tmp));
        } while (next_permutation(tmp.begin(), tmp.end()));
    }

    for (const auto& val : ans)
    {
        if (isPrime(val))
            answer++;
    }

    return answer;
}

　그 후 배열을 정렬하고, 현재 부분 문자열에 대해 모든 가능한 순열을 생성하고 이를 ans에 추가하는 부분이다. std::next_permutation()은 주어진 범위에서 다음 사전순 순열을 생성하고, 만약 다음 순열이 존재하지 않으면 false를 반환하는 함수다.
　마지막으로 배열에서 원소를 하나씩 꺼내어 소수를 만족하면 answer를 증가시키면 된다.

 

총합본

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

bool isPrime(int num)
{
    if (num <= 1)
        return false;

    if (num == 2 || num == 3)
        return true;

    if (num % 2 == 0 || num % 3 == 0)
        return false;

    for (int i = 5; i * i <= num; i += 6)
    {
        if (num % i == 0 || num % (i + 2) == 0)
            return false;
    }

    return true;
}

int solution(string numbers) 
{
    set<int> ans;
    int answer = 0;
    int n = numbers.size();

    for (int i = 1; i < (1 << n); ++i)
    {
        string tmp = "";

        for (int j = 0; j < n; ++j)
        {
            if ((i & (1 << j)) != 0)
                tmp += numbers[j];
        }

        sort(tmp.begin(), tmp.end());

        do
        {
            if (tmp[0] == '0')
                continue;

            ans.insert(stoi(tmp));
        } while (next_permutation(tmp.begin(), tmp.end()));
    }

    for (const auto& val : ans)
    {
        if (isPrime(val))
            answer++;
    }

    return answer;
}