[프로그래머스] 완전탐색 > 소수 찾기

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

소수 찾기라서 소수 알고리즘만 하면 될 줄 알았는데 나름 생각할 부분들이 있었다

알고리즘

1. 입력된 string의 길이를 이용하여 소수 탐색 범위 0~n 설정

• ex. 만약 숫자가 3개라면 세 자리의 소수까지 나올 수 있으므로 n을 1000으로 지정

2. 1부터 n까지 순차적으로 조회하면서, 해당 숫자가 numbers에 있으면서 소수인지 확인

배운 점

1. 세 가지의 소수 찾기 알고리즘

• 1) 2부터 n까지 나눠보고 나머지가 0이 되는 수가 없다면 소수로 판별
• 2) 1번의 방법에서 n의 절반까지만 확인하는 방법 (n의 절반보다 큰 수로 n을 나누었을 때 0이 나올 수가 없는 점 이용)
• 3) n의 양의 제곱근까지만 확인하는 방법 (가장 효율적)

2. string에서 지원하는 함수 복습

• string.find() 에서 npos를 반환하면 해당 문자가 없다는 의미
• string.erase(

전체 코드

#include <string>
#include <vector>
#include <iostream>
#include <string>
#include <cmath>
using namespace std;


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

bool IsNumbersMember(int num, string numbers) {
    string tempstr = numbers;
    string numstr = to_string(num);

    for(int i=0; i<numstr.length(); i++) {
        if(tempstr.find(numstr[i]) == string::npos) {
            return false;
        }
        else {
            tempstr.erase(tempstr.find(numstr[i]),1);
        }
    }
    return true;
}

int solution(string numbers) {
    int answer = 0;
    int n = 1;
    n = pow(10, numbers.length());

    for(int i=2; i<n; i++) {
        // 해당 숫자가 numbers에 있는지 확인
        if(IsNumbersMember(i, numbers)) {
            // 있다면 소수인지 확인
            if(IsPrimeNumber(i)) {
                answer++;
            }
        }      
    }

    return answer;
}

IsPrimeNumber(int num)

• 소수 탐색 범위를 num의 '양의 제곱근'까지로 지정
  -> 이 때, num의 '양의 제곱근'은 num의 약수들의 중간값이기도 함)
  -> 여기에선 pow()함수를 사용하지 않기 위해 i*i로 대체
• num의 양의 제곱근의 중간값으로 큰 숫자로 number를 나누었을 때 0이 나올 수 없기 때문
• 소수 찾기 알고리즘은 다음 블로그에서 여러 방식을 배울 수 있어 좋았다
  : 소수(Prime Number) 구하기 효율적 알고리즘 :: 코드자몽

bool IsNumbersMember(int num, string numbers)

• 숫자의 모든 자리수를 대상으로 numbers에 있는지 확인
• 확인된 숫자는 numbers에서 제거 (숫자 카드는 하나만 존재)
  1) 확인하려는 숫자를 string으로 변환
  2) string으로 변환된 숫자를 한 자리씩 탐색하면서 numbers에 있는지 확인
  -> 2-1) string.find()의 반환값이 npos이면 string에 없다는 의미이므로 false 반환
  -> 2-2) 있으면 중복 참조가 되지 않도록 string에서 삭제