[programmers] Lv.2 소수 찾기(c++)

와 드뎌 시간이 났다!!

 

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

using namespace std;

bool is_prime(int num){
    if(num <= 1) return false;
    
    for(int i=2; i<num/2 + 1; i++){
        if(num%i == 0) return false;
    }
    
    return true;
}

int solution(string numbers) {
    int answer = 0;
    sort(numbers.begin(), numbers.end());
    
    set<int> nums;
    do{
        string temp = numbers;
        while(!temp.empty()){
            nums.insert(stoi(temp));
            temp.pop_back();
        }
    }while(next_permutation(numbers.begin(), numbers.end()));
    
    for(auto s : nums){
        if(is_prime(s)) answer += 1;
    }
    
    return answer;
}

---

문제

https://programmers.co.kr/learn/courses/30/lessons/42839

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

728x90

---

[접근1]

소수인지 알아보는걸 먼저 만들자.

1과 0은 제외하고, 2부터 숫자/2까지의 숫자를 돌면서 나눠 떨어지면 소수가 아니고(false)

나누어 떨어지지 않으면 소수이다(true)

 

처음엔 숫자-1까지 돌았고, 이후엔 /2까지 해도 된다는것을 알았으며

다른 사람 풀이를 통해 sqrt(숫자) 까지 돌면 된다는 것을 알게되었다.

bool is_prime(int num){
    if(num <= 1) return false;
    
    for(int i=2; i<num/2 + 1; i++){
        if(num%i == 0) return false;
    }
    
    return true;
}

---

[접근2]

permutation을 돌기 위해 일단 sort를 해주었다.

만들 수 있는 숫자들을 저장하기 위해 set 변수를 만들었고,

permutation을 돌면서 해당 숫자에서 한자리수씩 제거해가며 set 변수에 넣어줬다. (모든 숫자 종이를 사용해야하는 것이 아니기 때문에..)

int solution(string numbers) {
    int answer = 0;
    sort(numbers.begin(), numbers.end());
    
    set<int> nums;
    do{
        string temp = numbers;
        while(!temp.empty()){
            nums.insert(stoi(temp));
            temp.pop_back();
        }
    }while(next_permutation(numbers.begin(), numbers.end()));
    
    ...
}

---

[접근3]

이렇게 구한 숫자들을 is_prime 함수에 넣어가며 확인하고, 소수이면 answer 값을 1 증가해준다.

int solution(string numbers) {
    ...
    
    for(auto s : nums){
        if(is_prime(s)) answer += 1;
    }
    
    return answer;
}