소수 찾기

🔒 문제

💭 생각의 흐름

제한 조건 : '0'으로 시작하는 자연수는 존재하지 않으므로 제외

(1) 조합 구하기

BFS based Branch & Bound 기법 사용으로 모든 조합 케이스를 구한다. 단, 제한 조건을 고려한다.

unorderd_set 자료구조를 사용하여 중복제거.
이미 조합에 포함된 (중복된) 케이스도 추가 검사를 하지 않음.
0으로 시작하는 케이스도 추가 검사를 하지 않음. (011 == 000011 == 11)

(2) 소수구하기

(1)에서 구한 집합들에 대해 SQRT (제곱근) 이하의 숫자까지만 검사하여 소수 판별

🔑 풀이

#include <string>
#include <vector>
#include <math.h>
#include <unordered_set>
#include <algorithm>
#include <string>
#include <queue>
using namespace std;

bool isPrimeNumber(unsigned int number) {
    if (number <= 1) return false;
    const unsigned int sqrtNumber = sqrt(number);
    for (unsigned int startNumber = 2; startNumber <= sqrtNumber ; startNumber++) {
        if (number % startNumber == 0) return false;
    }
    return true;
}

int solution(string numbers) {
    int answer = 0;
    sort(numbers.begin(), numbers.end());

    std::unordered_set<int> permutationsNumbers;
    std::queue<std::string> queue;

    //각 자리수별로 넣음, 0은 첫자리에 올 수 없으므로 제외 -> 0 첫자리에 온것은 무조건 제외됨.
    for (char singleNumber : numbers) {
        if(singleNumber != 0) queue.push(std::string(1, singleNumber));
    }

    //BFS based Branch and Bound
    while (!queue.empty()) {
        std::string targetString = queue.front();
        queue.pop();

        // 중복되지 않은 값만 서칭을 계속함.
        if (permutationsNumbers.find(std::stoi(targetString)) == permutationsNumbers.end()) {
            permutationsNumbers.insert(std::stoi(targetString));

            std::string sortedTargetString = targetString;
            sort(sortedTargetString.begin(), sortedTargetString.end());

            std::string remainString;
            // 현재 단계에서의 차집합을 구함
            std::set_difference(numbers.begin(), numbers.end(), sortedTargetString.begin(), sortedTargetString.end(), std::inserter(remainString, remainString.end()));

            for (char alphabet : remainString) {
                queue.push(targetString + alphabet);
            }
        }

    }

    for (auto number : permutationsNumbers) {
        if (isPrimeNumber(number)) answer++;
    }
    return answer;
}

추신

새삼 느끼는 거지만 C++은 진짜 컴퓨터(컴파일러) 입장에선 편할 지 몰라도
개발자 입장에선 문법이 너무 까다롭다.
set_difference 같은 라이브러리 함수는 이미 정렬된 집합에 대해서만 원하는 방식으로 작동한다.
가령 "CDEFAB" 와 "ABEF"의 차집합을 구하면 "EF"만 나온다 ㅡㅡ
그래서 따로 정렬 과정을 추가했다.
제시된 문자열의 길이가 짧은 편이기 때문에 속도에는 큰 영향을 미치지 않는다.