완전탐색 > 소수 찾기

문제 위치 : https://school.programmers.co.kr/learn/courses/30/lessons/42839

프로그래머스

이 문제도 두 가지 문제의 조합이다.

소수 판별과 브루트 포스를 통한 수의 조합이 그 두 가징다.

소수 판별의 경우 제곱수로 살펴보는 is_prime을 통해 쉽게 구현할 수 있다.

 

bool is_prime(int n) {
    if (n <= 1) return false;
    for (int i = 2; i * i <= n; i++) {
        if (n % i == 0) return false;
    }
    return true;
}

 

그 다음은 수의 조합을 만들어내는 것이다.

 

이를 위해서는 문자열을 활용하여 재귀적으로 구현하였다.

 

void generate_combinations(const string& current, string numbers, unordered_set<int>& primes) {
    if (!current.empty()) {
        int num = stoi(current);
        if (is_prime(num)) {
            primes.insert(num);
        }
    }
    for (size_t i = 0; i < numbers.size(); i++) {
        generate_combinations(current + numbers[i], numbers.substr(0, i) + numbers.substr(i + 1), primes);
    }
}

 

위 코드에 "123" 이라는 문자열을 넣는다면 아래와 같이 동작한다.

단계	current	numbers	변환된 정수	소수 여부	추가 여부
1	""	"123"	-	-	-
2	"1"	"23"	1	❌ (소수 아님)	추가 안 함
3	"12"	"3"	12	❌ (소수 아님)	추가 안 함
4	"123"	""	123	❌ (소수 아님)	추가 안 함
5	"13"	"2"	13	✅ (소수)	추가
6	"132"	""	132	❌ (소수 아님)	추가 안 함
7	"2"	"13"	2	✅ (소수)	추가
8	"21"	"3"	21	❌ (소수 아님)	추가 안 함
9	"213"	""	213	❌ (소수 아님)	추가 안 함
10	"23"	"1"	23	✅ (소수)	추가
11	"231"	""	231	❌ (소수 아님)	추가 안 함
12	"3"	"12"	3	✅ (소수)	추가
13	"31"	"2"	31	✅ (소수)	추가
14	"312"	""	312	❌ (소수 아님)	추가 안 함
15	"32"	"1"	32	❌ (소수 아님)	추가 안 함
16	"321"	""	321	❌ (소수 아님)	추가 안 함

 

이렇게 모든 수를 만들며 소수 여부 판별 후 primes 목록에 추가 되므로 최종 값은 primes의 크기가 된다.

#include <string>
#include <vector>
#include <unordered_set>
#include <algorithm>

using namespace std;

bool is_prime(int n) {
    if (n <= 1) return false;
    for (int i = 2; i * i <= n; i++) {
        if (n % i == 0) return false;
    }
    return true;
}

void generate_combinations(const string& current, string numbers, unordered_set<int>& primes) {
    if (!current.empty()) {
        int num = stoi(current);
        if (is_prime(num)) {
            primes.insert(num);
        }
    }
    for (size_t i = 0; i < numbers.size(); i++) {
        generate_combinations(current + numbers[i], numbers.substr(0, i) + numbers.substr(i + 1), primes);
    }
}

int solution(string numbers) {
    unordered_set<int> primes;
    generate_combinations("", numbers, primes);
    return primes.size();
}