C++ Algorithm Study 03/10 - 완전탐색 ( 프로그래머스 소수찾기 )

Study Day 03 완전탐색

문제: 프로그래머스 - [모의고사], [소수 찾기], [카펫]
programmers.co.kr/learn/courses/30/parts/12230

내 코드:
github.com/21600212/CodingTest/tree/master/Programmers/BruteForce

배운 것:
max_element(v.begin(),v.end()); // 최댓값을 반환한다. 1번 문제에서 *max_element()를 사용하면 깔끔하게 코딩이 가능하다.
Vector안의 원소로 Permutation(순열)과 Combination(조합)을 만드는 함수를 실제로 구현해봤다.

소수 찾기 문제가 특별히 어려웠는데 next_permutation을 이용해서 조합을 구하는 동시에 size를 줄여가면서 가능한 모든 경우의 수를 찾아야 했다. 이 과정에서 찾게 되는 소수 값들은 중복 될 수 있기 때문에 unique 함수를 사용해서 중복도 없애줘야 한다.

#include <string>
#include <vector>
#include <iostream>
#include <algorithm>
#include <cmath>
 
using namespace std;
 
bool is_prime(int num){
    if(num<=1) return false;
    for(int i=2; i<num; ++i)
        if(num%i==0) return false;
    return true;
}
 
int solution(string numbers) {
    int answer = 0;
    vector<int> primes;
 
    for(int size=1; size<=numbers.size(); ++size){
        vector<int> comb(numbers.size());
        for(int i=0; i<size; ++i){
            comb[i] = i+1;
        }
        sort(comb.begin(), comb.end());
        do{
            int num = 0;
            for(int i=0; i<comb.size(); i++){
                num += (numbers[i] - '0') * pow(10, comb[i]-1);
            }
            if(is_prime(num))
                primes.push_back(num);
        }while(next_permutation(comb.begin(),comb.end()));
    }
 
    sort(primes.begin(), primes.end());
    primes.erase(unique(primes.begin(),primes.end()),primes.end());
 
    return primes.size();
}

 

참고자료: