[프로그래머스 c++] 소수 찾기

문제 설명

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

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

제한사항

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

입출력 예

numbersreturn

17	3
011	2

입출력 예 설명

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

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

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

풀이방법

주어진 numbers로부터 만들 수 있는 가장 큰 값을 max라는 변수에 저장합니다.

그 후, 에라토스테네스의 체 알고리즘을 사용하여 2부터 max까지 숫자들의 소수 여부를 판단합니다.

(에라토스테네스의 체에 대한 부가 설명은 본문 아래를 참고해주세요.)

판단 결과는 isPrime에 반영됩니다.

체 알고리즘인 for 문을 돌면서 isPrime이 true인 값을 만나면 소수라고 판단하고, 해당 값(i)이 numbers에 포함된 숫자만을 이용하여 이루어진 숫자인지 판단합니다.

이를 판단하는 함수는 allUsed입니다.

allUsed는 numbers에 특정 값(i)의 각 자릿수가 numbers에 포함되어있는지 판단합니다.

만약 포함되어있다면 numbers에서 해당 숫자를 삭제해 중복 사용을 막습니다.

만약 포함되어있지 않다면 false를 return 합니다.

특정 값(i)의 모든 자릿수 숫자가 numbers에 포함되어있다면 true를 return 하고 answer를 하나 증가시킵니다.

 

#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <cmath>
 
using namespace std;
 
vector <int> v;
bool allUsed(int i, string numbers);
 
int solution(string numbers) {
    int answer = 0;
    int max = 0;
    
    // numbers 각 자리 수를 v에 넣기
    for (int i = 0; i < numbers.size(); i++) {
        v.push_back(stoi(numbers.substr(i, 1)));
    }
    
    // numbers 숫자를 내림차순으로 정렬
    sort(v.begin(), v.end(), greater<int>());
    
    // max 구하기
    for (int i = 0; i < v.size(); i++) {
        max = max + (v[i] * pow(10, v.size() - 1 - i));
    }
    
    vector <bool> isPrime(max+1, true);
    
    // 완전 탐색
    for (int i = 2; i <= max; i++) {
        if (isPrime[i]) {
            // i가 numbers로 나타내어지는 숫자면 answer++ 
            if (allUsed(i, numbers)) {
                answer++;
            }
            
            // 소수 아닌 것들 false로
            for (int j = 2; i * j <= max; j++) {
                isPrime[i * j] = false;
            }
        }
    }
    
    return answer;
}
 
bool allUsed(int i, string numbers) {
    string si = to_string(i);
    vector<bool> visit(v.size(), false);
        
    for (int j = 0; j < si.size(); j++) {
        int index = numbers.find(si.substr(j, 1));
        
        // numbers에서 해당 숫자가 발견되지 않을 경우
        if (index >= numbers.size()) {
            return false;
        }
        else {
            numbers = numbers.substr(0, index) + numbers.substr(index + 1);
        }
    }
    
    return true;
}

 

에라토스테네스의 체

위 gif를 보시면 쉽게 이해할 수 있습니다.

2부터 N까지 숫자들의 소수 여부를 판단하기 위해서 체라는 개념을 도입합니다.

크기가 N+1이고 모두 true로 초기화 되어있으며 이름이 isPrime인 벡터가 존재했을 때, for문 내부 변수인 i를 2부터 N까지 1씩 증가시키며 for문을 돕니다.

만약 isPrime[i]가 true이면 i를 소수라고 판단하고 i의 모든 배수의 isPrime값을 false로 만듭니다.

만약 isPrime[i]가 false이면 i를 소수라고 판단하지 않고 i를 1 증가시켜 다음 숫자의 소수 판별로 넘어갑니다.

이 과정을 반복하면 2부터 N까지 소수들의 isPrime 값은 true이고 소수가 아닌 수의 isPrime 값은 false가 됩니다.