[프로그래머스, C++] 소수 찾기(완전탐색 파트)

문제 링크

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

 

 

 

풀이

// init과 // process로 나뉜다.

 

중복 없이 생성되는 set 컨테이너 이용

 

// init --- nums에 만들어질 숫자들 저장(사실 이때 소수판별 해도 됨)

// process --- 소수 판별 

 

// init

1)

1자리만 미리 set에 할당

- stoi()가 char형에 대해서 안되므로 string으로 casting

- atoi()로 할 수도 있지만 char*형으로 바꿔야 한다.

 

2)

2자리 이상에 대해서 숫자 만들기(next_permutation() 이용)

오름차순 sort를 먼저 해준다

- next_permutation() 하기 위해서, 내림차순 정렬하면 prev_permutation() 하면 된다.

- substr()로 2자리 이상씩 만들어서 set에 할당

 

// process --- 소수판별

소수판별은 2부터 해당 수의 제곱근이하까지 반복문을 돌면서 나누어 떨어지지 않는 점을 이용한다.

- sqrt() 함수 이용(<cmath>)

- 2미만은 소수가 아닌 것에 대해 미리 continue;

 

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

using namespace std;

int solution(string numbers) {
    int answer = 0;
    
    // init - nums에 만들어질 숫자 저장
    set<int> nums;        // 만들어진 숫자들(중복 X)
    
    // 1자리
    for(int i=0; i<numbers.length(); i++){
        string s = "";
        s += numbers[i];    // for casting
        nums.insert(stoi(s));       // 알아서 중복 제거
    }
    
    // 2자리 이상
    sort(numbers.begin(), numbers.end());       // for next_permutation()
    do{
        for(int i=2; i<=numbers.length(); i++){
            string s = numbers.substr(0, i);
            nums.insert(stoi(s));       // 알아서 중복 제거
        }
    }while(next_permutation(numbers.begin(), numbers.end()));
    
    // process
    for(auto e: nums){
        if(e < 2) continue;     // 2 미만은 소수X
        
        // 소수 판별(제곱근이하까지)
        bool check = true;
        for(int i=2; i<=sqrt(e); i++){
            if(e % i != 0) continue;
            check = false;
            break;
        }
        if(check) answer++;
    }
    
    return answer;      // 소수로 만들 수 있는 가짓 수
}