Gidhub BE Developer

[Programmers] 소수 찾기

2018-09-26
goodGid
Algorithm

Problem

Problem URL : 소수 찾기

[1] Answer Code (18. 09. 26)

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

bool p[10000000]; // p is Prime Number
bool c[10000000];

int solution(string s) {
    memset(p,1,sizeof(p));
    p[0] = false;
    p[1] = false;
    for(int i=2; i*i<10000000; i++){
        if(p[i] == false) continue;
        p[i] = true;
        for(int j=i*2; j<10000000; j+=i)
            p[j] = false;
    }
    
    int ans=0;
    int size = (int)s.size();
    sort(s.begin(),s.end());
    do{
        for(int i=1; i<=size; i++){
            int n;
            n = stoi(s.substr(0,i));
            if(!c[n] && p[n]){
                c[n] = true; // n값은 사용했다.
                ans++;
            }
        }
    } while(next_permutation(s.begin(),s.end()));
    return ans;
}

[2] Answer Code (18. 09. 26)

#include <iostream>
#include <cstring>
#include <set>
#include <algorithm>
using namespace std;

bool p[10000000]; // p is Prime Number

int solution(string s) {
    memset(p,1,sizeof(p));
    p[0] = false;
    p[1] = false;
    for(int i=2; i*i<10000000; i++){
        if(p[i] == false) continue;
        p[i] = true;
        for(int j=i*2; j<10000000; j+=i)
            p[j] = false;
    }
    
    set<int> se;
    int ans=0;
    int size = (int)s.size();
    sort(s.begin(),s.end());
    set<int>::iterator iter;
    
    do{
        for(int i=1; i<=size; i++){
            int n;
            n = stoi(s.substr(0,i));
            iter = se.find(n);
            if(iter == se.end() && p[n]){
                se.insert(n);
                ans++;
            }
        }
    } while(next_permutation(s.begin(),s.end()));
    return ans;
}
  • [STL] set을 사용한 풀이

[3] Answer Code (21. 01. 30)

class Solution {
    private String DEFAULT_NUMBER_BY_STRING_TYPE = "";
    boolean[] isPrime = new boolean[10_000_000];
    boolean[] isUsed = new boolean[10_000_000];
    HashMap<Integer, Integer> map = new HashMap<>();

    public int solution(String numbers) {
        init(10_000_000);

        char[] toCharArray = numbers.toCharArray();
        recur(toCharArray, toCharArray.length, 0, DEFAULT_NUMBER_BY_STRING_TYPE);
        return (int) map.keySet().stream().count();
    }

    private void recur(char[] toCharArray, int size, int idx, String numberByStringType) {
        if (idx == size) {
            if (DEFAULT_NUMBER_BY_STRING_TYPE.equals(numberByStringType)) {
                return;
            }

            Integer numberByIntegerType = Integer.valueOf(numberByStringType);

            if (numberByIntegerType == 0
                || numberByIntegerType == 1) {
                return;
            }

            if (isPrime[numberByIntegerType]) {
                map.put(numberByIntegerType, 1);
            }
            return;
        }

        for (int i = 0; i < size; i++) {
            if (isUsed[i]) {
                continue;
            }
            // Use
            isUsed[i] = true;
            recur(toCharArray, size, idx + 1, numberByStringType + toCharArray[i]);

            // Not use
            isUsed[i] = false;
            recur(toCharArray, size, idx + 1, numberByStringType);
        }
    }

    private void init(int n) {
        Arrays.fill(isPrime, true);

        for (int i = 4; i < n; i += 2) {
            isPrime[i] = false;
        }

        for (int i = 3; i < Math.sqrt(n); i += 2) {
            if (isPrime[i]) {
                for (int j = 3; i * j < n; j += 2) {
                    isPrime[i * j] = false;
                }
            }
        }
    }
}

  • 소수를 미리 구해놓고

    Recursive 하게 문제의 조건을 구한다.

Recommend

Index