[Level 2] 소수 찾기 - 완전 탐색 | C++

[문제]

인자로 0~9의 연속된 문자열이 주어지는데, 각 숫자(문자)로 만들 수 있는 소수(prime number)의 수를 구하는 문제이다. 레벨은 낮은데 뭔가 접근하기가 어려워서 구글링을 하던 도중 에라토스테네스의 체라는  알고리듬에서 아이디어를 얻었다. 에라토스테네스의 체는 간단하게 말해서 소수를 구하는 방법인데, 구하고자 하는 구간의 값을 모두 구한 뒤 그 중에서 소수가 아닌 수를 걸러내는 방법이다.

나는 위 문제에서 주어진 값을 내림차순으로 정렬하여, 주어진 수로 만들 수 있는 최대 값을 구하고, 해당 값 이하의 모든 값을 구하여 그 중에서 소수를 걸러내었다. 그리고 그 소수 중 주어진 수로 만들 수 있는 개수를 구하였다. 요약해서 단계로 나타내면 다음과 같다.

1. 주어진 문자열(numbers)를 1개씩 쪼개서 벡터에 저장 후 내림차순 정렬
   i.e) "17" -> 1, 7 -> 7, 1
2. 정렬한 순서 그대로 이어서 최대값을 구한다.
   i.e) 7, 1 -> 71 
3. 71이하의 모든 소수를 구한다.
   i.e) 2, 3, 5, 7, 11, ...., 71
4. 3번에서 구한 소수 중 주어진 문자열로 만들 수 있는 소수의 수를 구한다.

 

[코드]

#include <string>
#include <vector>
#include <list>
#include <unordered_set>
#include <algorithm>        // sort
#include <cstdlib>          // atoi
#include <cmath>            // sqrt

using namespace std;

bool IsPrime(const uint32_t num);
bool IsContain(const uint32_t num, const unordered_multiset<char>& set);

int solution(string numbers) 
{
    int answer = 0;
    
    // numbers를 각 숫자로 나누어 벡터에 저장 
    vector<uint32_t> nums;
    unordered_multiset<char> set;
    
    size_t size = numbers.size();
    nums.reserve(size);
    set.reserve(size);
    
    for(const auto myChar : numbers)
    {
        nums.push_back(myChar - '0');
        set.insert(myChar);
    }
    
    // 내림차순으로 정렬 후 연속되는 값으로 만듭니다.
    // i.e. [3,2,1] -> 321
    sort(nums.begin(), nums.end(), greater<size_t>());

    string maxNumStr = "";
    for(const auto num : nums)
    {
        maxNumStr += num + '0';
    }
    uint32_t maxNum = atoi(maxNumStr.c_str());
    
    // 2부터 321(maxNum)까지의 소수를 모두 구합니다.
    list<uint32_t> primeNum;
    for(uint32_t i = 2; i <= maxNum; ++i)
    {
        // i가 소수라면 리스트에 추가
        if(IsPrime(i)) 
            primeNum.push_back(i);
    }
    
    // 구한 소수가 주어진 문자열(숫자)로 만들 수 있는지 확인
    for(const auto num : primeNum)
    {
        // 만들 수 있다면 카운트 증가
        if(IsContain(num, set)) 
            ++answer;
    }
    
    return answer;
}

// num이 소수인지 확인합니다. 
bool IsPrime(const uint32_t num)
{
    uint32_t root = sqrt(num);
    for(size_t i = 2; i <= root; ++i)
    {
        if(num % i == 0)
            return false;
    }
    
    return true;
}

// num이 주어진 문자열로 만들 수 있는 수인지 확인합니다.
bool IsContain(const uint32_t num, const unordered_multiset<char>& set)
{
    string tmpStr = to_string(num);
    unordered_multiset<char> tmpSet = set;
    unordered_multiset<char>::iterator iter;
    for(const auto myChar : tmpStr)
    {
        // 일치하는 문자를 찾지 못했다면 false 반환
        if(tmpSet.find(myChar) == tmpSet.end())
            return false;
        else 
        {
            /* 
                문자가 중복 사용되어 통과되는 경우가 없도록 삭제합니다.
                i.e. 주어진 문자열이 "17"일 때 소수 11을 만들 수 있는지 확인할 경우
                1을 체크 후 멀티셋에서 1을 삭제하여, 1이 1개보다 많이 사용되는 경우를 막습니다.
            */   
            iter = tmpSet.find(myChar);
            tmpSet.erase(iter);
        }
    }
    
    return true;
}

주어진 문자열로 만들 수 있는 소수인지 확인할 때, 해시(멀티)셋을 사용함으로써 검색 속도를 높였다. 예를 들어 문자열 "17"이 주어졌을 때, 소수 11이 주어진 문자열로 만들 수 있는 수인지 확인한다고 생각해보자. 멀티셋엔 ['1', '7']이 저장되어 있고 소수 11의 각 자리 수가 멀티셋에 존재하는 지 확인할 때,  해시 함수의 특성 상 평균 상수 시간에 확인할 수 있다.

단순 셋이 아닌 멀티셋으로 한 이유는 중복되는 값 사용을 막기 위해서다. 예를 들어 1과 7로 11을 만들 수 있는지 확인하기 위해선 1의 중복된 사용을 체크해야 한다. 때문에 멀티셋을 사용하여 "117" 일 경우 동일한 수의 저장을 허락하고, 값을 체크할 때 마다 삭제하여 이미 사용된 값의 중복 사용을 막는다.