[프로그래머스]K 진수에서 소수 개수 구하기
📒활용 개념
📌문제설명
양의 정수n에 대하여 k진수로 바꿨을 때, 변환된 수 안에 조건에 맞는 소수가 몇 개인지 구하라.
조건
- 0p0처럼 소수 양쪽이 0인경우
- p0처럼 소수 오른쪽에만 0이 있고 왼쪽에는 아무 것도 없는 경우
- 0p처럼 소수 왼쪽에만 0이 있고 오른쪽에는 아무 것도 없는 경우
- 단,p는 각 자릿수에 0을 포함하지 않는 소수
--> 결국 0을 기준으로 소수를 분리해라.
📌구현
#include <string>
#include <vector>
#include <stack>
using namespace std;
string number="0123456789ABCDEF"; //진수 표현 위한 num
string change (int num, int binary){ //진수 변환 함수(설명->활용개념 링크 참조)
string result;
if(num == 0){
return "0";
}
while(num > 0){
result = number[num % binary]+result;
num /= binary;
}
return result;
}
bool check (long int dec){ //소수 확인 함수(설명->활용개념 링크 참조)
if(dec<2){
return false;
}
else{
for(long int i=2; i*i<=dec; i++){
if(dec%i==0){
return false;
}
}
}
return true;
}
int solution(int n, int k) {
int answer = 0;
string s_total; //진수변환과 int to string 이후 string
string sum;
vector<string> split; //split이후 string
s_total=change(n, k);
for(int i=0; i<s_total.size(); i++){ //'0'을 기준으로 split
if(s_total[i]=='0'){
if(sum!=""){
split.push_back(sum);
sum="";
}
}
else{
sum+=s_total[i];
}
}
if(sum!=""){ //왼쪽에만 0이 있는 경우 push_back
split.push_back(sum);
}
for(int i=0; i<split.size(); i++){ //split된 string 소수인지 확인
if(check(stoll(split[i]))){
answer++;
}
}
return answer;
}
📌주의점
- 문제를 읽고 사용해야하는 함수에 대한 흐름 파악.
- n의 범위에 따라 stoi가 아닌 stoll사용.
- 소수인지 파악.
- 정확한 진수 변환.
Author And Source
이 문제에 관하여([프로그래머스]K 진수에서 소수 개수 구하기), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@gomhyeok/프로그래머스K-진수에서-소수-개수-구하기저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)