[Programmers/C++] 소수 찾기

 

문제

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

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

 

제한 사항

 

 

 

입출력 예시

입출력 예시

 

입출력 예시

 

 

 

---

 

풀이 

• 완전 탐색(Brute Force)을 이용해 모든 가능한 조합을 생성하고, int형으로 변환하여 set<int> 에 담았다.
• set에 저장함으로서, 중복(예: 011과 11은 동일한 숫자로 취급)을 제거했다.

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

set<int> combinations;

/* 숫자 조합 */
void generateCombination(string current, string remaining) {
    if (!current.empty()) {
        combinations.insert(stoi(current));
    }

    if (remaining.empty()) return;

    for (int i = 0; i < remaining.length(); ++i) {
        generateCombination(current + remaining[i], remaining.substr(0, i) + remaining.substr(i + 1));
    }
}

int solution(string numbers) {
    generateCombination("", numbers);

    /* 소수 판별 및 카운트 */
    int answer = combinations.size();
    for (const auto& num : combinations) {
        /* 0과 1은 소수가 아님 */
        if (num <= 1) {
            answer--;
            continue;
        }

        /* 2는 소수 */
        if (num == 2)
            continue;

        /* 2를 제외한 짝수는 소수가 아님 */
        if (num % 2 == 0) {
            answer--;
            continue;
        }
            
        /* 3부터 num의 제곱근까지 소수 판별 */
        for (int i = 3; i * i <= num; ++i) {
            if (num % i == 0) {
                answer--;
                break;
            }
        }
    }

    return answer;
}

 

 

 

---