프로그래머스 완전탐색 소수찾기 c++

문제 링크 : https://programmers.co.kr/learn/courses/30/lessons/42839#

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

 

코드

#include <string>
#include <map>
#include <algorithm>
#include <cmath>

using namespace std;

map<int, bool> M;

bool isPrime(string num){
    int n = stoi(num);
    
    if(M[n]) return false; // 이미 확인한 수라면 중복이기 때문에 false 리턴
    M[n] = true;
    if(n == 1 || n == 0) return false;
    if(n == 2) return true;
    
    for(int i=2; i<=sqrt(n); i++){
        if(n % i == 0){ 
            M[n] == -1;
            return false;
        }              
    }
    M[n] == 1;
    return true;
}

int solution(string numbers) {
    int answer = 0;
    // 오름차순 정렬
    sort(numbers.begin(), numbers.end());
    // 나올 수 있는 모든 조합에 대해서
    // 한 자리수인 경우, 두 자리수인 경우, ..., numbers.size() 자리수인 경우
    // 를 모두 검사
    do{
        for(int i=1; i<=numbers.size(); i++){
            string num = numbers.substr(0, i);         
            if(isPrime(num)) answer++;
        }
    }while(next_permutation(numbers.begin(), numbers.end()));
    
    return answer;
}

 

해설

전체적인 흐름은 이렇다.

 

1. do{}whlie(next_permutation....) 을 통해 주어진 string에 대해서 나올 수 있는 모든 조합을 얻는다.

 

2. 그 반복문 안에서 for문을 통해 얻을 수 있는 모든 자리 수에 대해 소수를 검사한다.

  예를 들어 이번 string이 5412이라면,

  5, 54, 541, 5412에 대해서 검사하는 것이다.

  1, 421 같은 다른 숫자에 대해선 어차피 다른 조합에서 무조건 나올 것이기 때문에 고려하지 않아도 된다.

 

3. 소수인지 검사할 때는 자신의 제곱근 수 까지만 검사한다. 

 

4. 중복된 수에 대한 소수 검사를 방지하기 위해 map을 이용해 이미 검사했던 수인지 체크한다

 

=====

 

다른 사람들 풀이보다 깔끔한 것 같아서 만족스럽다.