[c++] 프로그래머스: 완전탐색 / 소수 찾기

문제 설명

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

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

제한사항

• numbers는 길이 1 이상 7 이하인 문자열입니다.
• numbers는 0~9까지 숫자만으로 이루어져 있습니다.
• 013은 0, 1, 3 숫자가 적힌 종이 조각이 흩어져있다는 의미입니다.

입출력 예

numbers	return
17	3
011	2

입출력 예 설명

예제 #1
[1, 7]으로는 소수 [7, 17, 71]를 만들 수 있습니다.

예제 #2
[0, 1, 1]으로는 소수 [11, 101]를 만들 수 있습니다.

• 11과 011은 같은 숫자로 취급합니다.

문제풀이

1. 주어진 numbers 문자열을 내림차순 정렬한다.

2. 정렬된 numbers 문자열을 숫자로 변환한다.

3. 변환된 숫자는 문자열 조합으로 만들 수 있는 최대수이다. 그러므로 0부터 변환된 숫자까지의 수들을 검사한다.

4. 그 중, 소수이며, numbers 문자들로 구성될 수 있는 수를 찾아낸다.

 

Solution.cpp

1) 소수 판별시 sqrt()를 쓴 경우

#include <string>
#include <vector>
#include <algorithm>
#include <functional>

using namespace std;

// 소수 판별
bool isPrime(int num)
{
    if(num<2) // 0과 1은 소수에서 제외
        return false;
    for(int i=2; i<=sqrt(num); i++) // 2부터 주어진 수의 제곱근까지 포함하여 겁사
        if(num%i==0) // 나누어 떨어지면 소수가 아님
            return false;
    return true;
}

// 숫자가 주어진 문자들로 구성 가능한지 판별
bool isIncluded(int num, string str)
{
    string strNum = to_string(num); // 숫자를 문자열로 변환
    for(int i=0; i<strNum.size(); i++) {
        int flag = false;
        for(int j=0; j<str.size(); j++) {
            if(strNum.at(i) == str.at(j)) { // 일치하는 문자가 있다면
                flag = true;
                str.at(j) = ' '; // 해당 문자를 공백으로 대체, 또 사용할 수 없게
                break;
            }
        }
        if(!flag) // 한번이라도 일치하는 문자가 없는 경우 false 리턴
            return false;
    }
    return true;
}

int solution(string numbers) {
    int answer = 0;
    
    sort(numbers.begin(), numbers.end(), greater<int>()); // 문자 큰 순서로 정렬
    int maxNum = stoi(numbers); // 문자열을 숫자로 변환
    
    for(int i=0; i<=maxNum; i++) { // 가장 큰수까지의 숫자들을 검사
        if(isPrime(i) && isIncluded(i, numbers)) { // 소수이고, 갖고있는 문자로 구성할 수 있는 수 판별
            answer++;
        }
    }
    return answer;
}

 

 

2) 소수 판별시 에라토스테네스의 체를 이용한 경우

#include <string>
#include <vector>
#include <algorithm>
#include <functional>

using namespace std;

bool *primeArr;

// 에라토스테네스의 체: 소수 판별 배열 만들기
void Eratos(int num)
{   
    primeArr = new bool[num+1]; // 소수판별 배열 할당
    
    // 0과 1을 false로 바꿔줘야 예제#2를 통과할 수 있음
    primeArr[0] = false;
    primeArr[1] = false;
    
    // 모두 일단 true로 초기화
    for(int i=2; i<=num; i++)
        primeArr[i] = true;
    
    for(int i=2; i*i<=num; i++) {
        if(primeArr[i]) // 만약 처음 수가 true이면(소수이면)
            for(int j=i*i; j<=num; j+=i)
                primeArr[j] = false; // 그 배수를 false로 바꿔주기(소수의 배수는 소수가 아님)
    }
    
}

// 숫자가 주어진 문자들로 구성 가능한지 판별
bool isIncluded(int num, string str)
{
    string strNum = to_string(num); // 숫자를 문자열로 변환
    for(int i=0; i<strNum.size(); i++) {
        int flag = false;
        for(int j=0; j<str.size(); j++) {
            if(strNum.at(i) == str.at(j)) { // 일치하는 문자가 있다면
                flag = true;
                str.at(j) = ' '; // 해당 문자를 공백으로 대체, 또 사용할 수 없게
                break;
            }
        }
        if(!flag) // 한번이라도 일치하는 문자가 없는 경우 false 리턴
            return false;
    }
    return true;
}

int solution(string numbers) {
    int answer = 0;
    
    sort(numbers.begin(), numbers.end(), greater<int>()); // 문자 큰 순서로 정렬
    int maxNum = stoi(numbers); // 문자열을 숫자로 변환
    
    Eratos(maxNum); // 소수판별 배열 만들기
    for(int i=0; i<=maxNum; i++) { // 가장 큰수까지의 숫자들을 검사
        if(primeArr[i] && isIncluded(i, numbers)) { // 소수이고, 갖고있는 문자로 구성할 수 있는 수 판별
            answer++;
        }
    }
    return answer;
}

문제 출처: https://programmers.co.kr/learn/courses/30/lessons/42839