[ 프로그래머스 ] 소수 찾기 ( 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은 같은 숫자로 취급합니다.

 

 

 

<내 풀이>

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

using namespace std;

int solution(string numbers) {
    int answer = 0, max = 0;
    int d[9999999] = {0,};
    vector<int> n(10,0);
    
    sort(numbers.begin(), numbers.end(), greater<>());
    max = stoi(numbers);
    
    for(int i=2; i<=max; i++){
        if(d[i] == 1) continue;
        for(int j=i+i; j<=max; j+=i){
            d[j] = 1;
        }
    }
    
    for(int i=0; i<numbers.size(); i++){
        n[numbers[i]-'0']++;
    }
    
    for(int i=2; i<=max; i++){
        if(d[i] != 0) continue;
        string a = to_string(i);
        vector<int> nn = n;
        for(int j=0; j<a.size(); j++){
            if(nn[a[j]-'0'] == 0) break;
            nn[a[j]-'0']--;
            if(j == a.size()-1) answer++;
        }
    }
    
    return answer;
}

일단, 나는 소수를 찾는 데 있어서 에라토스테네스의 체 알고리즘을 사용했다.

1. 주어진 문자열에서 구할 수 있는 가장 큰 max 값을 구한다.

2. 2부터 max값까지 에라토스테네스의 체 알고리즘을 사용하여 소수를 걸러낸다. 이 때 배열 d에서 값이 0으로 남는 인덱스는 소수이다.

3. numbers에서 각 자리의 숫자 갯수를 배열 n에 저장한다.

4. 다시 2부터 max값까지 for문을 돌면서 소수인 값을 string으로 바꾼다. 바꾼 문자열 값의 각 자릿수가 numbers에 있는지 배열 n의 값으로 확인하고 모두 있다면, answer값을 증가시킨다.

 

즉, 나는 소수인 값들을 걸러낸 다음 numbers에 그 수가 있는지 확인하는 방법을 사용했다.

그런데 여러 사람들의 풀이를 공부하는데, 새로운 것들을 많이 배웠다.

이것들을 사용하여 훨씬 더 좋은 성능을 낼 수 있었다.

 

 

+) 새롭게 배운 지식 

1. 어떤 숫자(n)를 소수인지 판별하기 위한 방법으로 for문을 사용할 때

2부터 해당 숫자(n)까지 나누어지는 수가 있으면 소수가 아니다. 이 때 n까지 for문을 돌릴 필요 없이 제곱근( sqrt(n) )까지만 돌려도 된다. 예를 들어 8은 2*4 이면서 4*2이다. 즉, 2에서 한번 검사 후 다시 4를 또 검사할 필요가 없다는 의미이다.

 

2. next_permutation 함수

순열 함수이다. 자세한 내용은 새롭게 글을 올리려하니 아래 링크를 참고하자.

2021/01/12 - [C++] - [ C++ ] 순열을 구할 수 있는 함수 next_permutation

이 함수를 이용하여 numbers의 숫자들로 만들 수 있는 모든 수를 구할 수 있는 것이다.

 

 

 

 

<새롭게 만든 풀이>

#include <string>
#include <algorithm>
#include <unordered_set>
#include <cmath>

using namespace std;

int checkPrime(int n) {
    if(n==0 || n==1) return 0;
    for(int i=2; i<=sqrt(n); i++){
        if(n % i == 0) return 0;
    }
    return 1;
}

int solution(string numbers) {
    unordered_set<int> uos;
    int x = 0;

    sort(numbers.begin(), numbers.end());
    do {
    	for(int i=1; i<numbers.size()+1; i++){
            x = stoi(numbers.substr(0, i));
            if(checkPrime(x)) uos.insert(x);
        }
    } while(next_permutation(numbers.begin(), numbers.end()));
    
    return uos.size();
}

1. next_permutation 함수를 통해 numbers의 값들을 다음 순열로 바꾼다. 

2. substr 함수를 사용하여 numbers의 값을 크기별로 자른 값이 소수인지 판별한다.

3. for문을 2부터 n의 제곱근까지 돌려서 나누어지는 값이 있는지 없는지 여부를 통해 소수인지 판별한다.

4. 위에서 소수라고 판별되었다면 unordered_set에 넣는다.

5. unordered_set 의 크기를 반환한다.