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

코딩테스트 연습 - 소수 찾기

풀이

1. 종이 조각으로 만들 수 있는 모든 숫자들 찾기
2. 그 숫자들 중에 소수가 몇 개 인지 확인하기

가능한 모든 숫자 조합들을 찾기 위해서 백트래킹을 사용했고, 11과 011은 같은 숫자로 취급해서 unordered_set을 통해 중복도 제거해줬다.
이렇게 얻은 숫자들을 어떻게 소수 판별을 해줄까? 생각했는데, 단순하게 2부터 숫자/2까지의 수들로 다 나눠봐서 나눠지지 않으면 소수라고 생각했다.

+) 새롭게 배운 사실

• 다른 풀이들을 봤는데, 소수를 찾을 때 2부터 sqrt(숫자)까지만 나눠주면 더 빠르게 정답을 구할 수 있다!
  -> 다음에 소수 찾는 문제가 나온다면 제곱근까지 확인해주자

• 소수 찾기, 검사할 때 쓰이는 알고리즘 -> 에라토스테네스의 체

에라토스테네스의 체

만약 1부터 10000 중에 소수를 찾는다고 한다면,

int size = 10000;

// 1. 배열(벡터) 생성 후 초기화 해주기
int arr[size + 1];

// true로 초기화 해도 되고 1로 초기화 해도 되고 초기화 하는 방법은 다양하다.
for(int i = 2 ; i <= size ; i++) arr[i] = i;

// 2. 체로 합성수들 걸러내기
for(int i = 2 ; i * i <= size ; i++){
	// 이미 0으로 표시된 수는 소수가 아니므로 넘어간다.
	if(arr[i] == 0) continue;
    
    // i의 배수들을 표시해준다.
    for(int j = i + i ; j <= size ; j += i){
    	arr[j] = 0;
    }
}

// 3. arr 배열을 통해 소수들을 확인할 수 있다.

코드

처음 코드

#include <string>
#include <vector>
#include <unordered_set>
using namespace std;

unordered_set <int> s;
string str = "";
bool check[7];

void find_all_numbers(int depth, int limit, string& numbers){
    if(depth == limit) return;
    
    for(int i = 0 ; i < limit ; i++){
        if(!check[i]){
            check[i] = true;
            str.push_back(numbers[i]);
            s.insert(stoi(str));
            find_all_numbers(depth+1, limit, numbers);
            str.pop_back();
            check[i] = false;
        }
    }
}
int solution(string numbers) {
    int size = numbers.size();
    
    find_all_numbers(0,size, numbers);
    
    int answer = 0;
    
    for(auto& it : s){
        if(it == 1 || it == 0) continue;
        
        int num = it / 2;
        bool isDivided = false;
        for(int i = 2 ; i <= num ; i++){
            if(it % i == 0) isDivided = true;
        }
        if(!isDivided) answer++;
    }
    
    return answer;
}

sqrt 사용한 코드

#include <iostream>
#include <string>
#include <vector>
#include <unordered_set>
#include <cmath>
using namespace std;

unordered_set <int> s;
string str = "";
bool check[7];

void find_all_numbers(int depth, int limit, string& numbers){
    if(depth == limit) return;
    
    for(int i = 0 ; i < limit ; i++){
        if(!check[i]){
            check[i] = true;
            str.push_back(numbers[i]);
            s.insert(stoi(str));
            find_all_numbers(depth+1, limit, numbers);
            str.pop_back();
            check[i] = false;
        }
    }
}
int solution(string numbers) {
    int size = numbers.size();
    
    find_all_numbers(0,size, numbers);
    
    int answer = 0;
    
    for(auto& it : s){
        if(it == 1 || it == 0) continue;
        
        int num = sqrt(it);
        // sqrt를 사용하지 않고, 
        // for(int i = 2 ; i*i <= it ; i++){ }을 쓰는 방법도 있다.
        bool isDivided = false;
        for(int i = 2 ; i <= num ; i++){
            if(it % i == 0) isDivided = true;
        }
        if(!isDivided) answer++;
    }
    
    return answer;
}