[c++/프로그래머스] k진수에서 소수 개수 구하기

문제 링크

k진수에서 소수 개수 구하기

풀이

stringstream으로 문자열 나누고 소수인지 구하는 문제
1. k진수 구하기
1-1. n을 k로 나누면서 나머지는 저장하고 n이 0이 될 때 까지 반복한다.
1-2. 저장된 나머지들을 reverse로 뒤집으면 k진수 변환 완료, string으로 바꾸어 return한다.
2. stringstream과 getline으로 0기준으로 나눈다.
2-1. 나누어진 숫자들은 소수인지 판별하는데, 2부터 제곱근 n까지 하면 시간 복잡도 루트n으로 할 수 있음.
2-3. 나누어 떨어지면 소수가 아닌거고, 끝까지 나누어 떨어지지 않으면 소수이다.

주의할 점은 k진수로 바꾼 문자열은 엄청 길기 때문에 형을 long long으로 변환해야 한다.

코드

#include <string>
#include <vector>
#include <iostream>
#include <algorithm>
#include <sstream>
#include <cmath>

using namespace std;

string func(int &n, int &k)
{
    vector<int> v;
    while(n>0)
    {
        v.push_back(n%k);
        n/=k;
    }
    reverse(v.begin(), v.end());
    
    string s = "";
    for(int i=0;i<v.size();i++)
    {
        s+=to_string(v[i]);
    }
    return s;
}

bool sosu(string v)
{
    if(v=="") return false;
    
    long long n = stoll(v);
    if(n==0 || n==1) return false;
    
    bool flag = true;
    for(long long i=2;i<=sqrt(n);i++)
    {
        if(n%i==0)
        {
            flag = false;
            break;
        }
    }
    
    return flag;
}

int solution(int n, int k) {
    int answer = 0;
    
    string s = func(n,k);
    
    string tmp;
    stringstream stream(s);
    while(getline(stream, tmp, '0'))
    {
        answer += sosu(tmp);
    }
    
    return answer;
}