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

 

 

 

 

 

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

프로그래머스

 

이번 문제는 완전 탐색 문제였습니다.

 

 

 

 

📝 문제 풀이

1. numbers의 각 문자를 char 타입의 v 벡터에 삽입

2. next_permutation 함수를 사용하기 위해 v 벡터를 오름차순으로 정렬

3. next_permutation을 사용하여 v 벡터의 다음 순열을 구하면서 1자리수 ~ numbers.length()자리수까지의 모든 숫자를 nums 벡터에 삽입

4. sort 함수, earse 함수, unique 함수를 사용하여 nums 벡터의 중복 값을 모두 제거 ⭐️

5. nums 배열에서 소수를 찾아 소수만 담은 배열 반환

 

 

 

 

👩🏻‍💻 C++ 코드

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

using namespace std;

int countPrime(vector<int> &nums) {
    int cnt = nums.size();
    
    for (int i=0; i<nums.size(); i++) {
        if (nums[i] <= 1) cnt--;
        
        for (int j=2; j*j<=nums[i]; j++) {
            if (nums[i] % j == 0) {
                cnt--;
                break;
            }
        }
    }
    
    return cnt;
}

int solution(string numbers) {
    vector<char> v;
    vector<int> nums; // 종이 조각으로 만들 수 있는 모든 숫자들
    
    for (int i=0; i<numbers.length(); i++)
        v.push_back(numbers[i]);
    
    sort(v.begin(), v.end());
    
    do {
        string acc = "";
        
        for (int i=0; i<v.size(); i++) {
            acc += v[i];
            nums.push_back(stoi(acc)); // 1자리수~최대자리수까지 모두 삽입
        }
        
    } while (next_permutation(v.begin(), v.end()));
    
    // 중복된 숫자 제거
    sort(nums.begin(), nums.end());
    nums.erase(unique(nums.begin(), nums.end()), nums.end());
    
    int answer = countPrime(nums);
    
    return answer;
}

 

프로그래머스 - 결과 화면