[프로그래머스] 완전탐색 > 소수 찾기
3491 단어 완전탐색programmersprogrammers
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의 양의 제곱근까지만 확인하는 방법 (가장 효율적)
- 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에서 삭제
Author And Source
이 문제에 관하여([프로그래머스] 완전탐색 > 소수 찾기), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@minjujuu/프로그래머스-완전탐색-소수-찾기저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)