[Algorithm] Programmers :: k진수에서 소수 개수 구하기

https://school.programmers.co.kr/learn/courses/30/lessons/92335

프로그래머스

bool checkPrimeNum(long long n)
{
    if (n < 2) return false;
 
    for (long long i = 2; i < (long long)sqrt(n); i++)
    {
        if ((n % i) == 0)
        {
            return false;
        }
    }
 
    return true;
}
 
vector<string> divide(string s)
{
    istringstream ss(s);
    string subs1;
    vector<string> v;
 
    while (getline(ss, subs1, '0'))
    {
        v.push_back(subs1);
    }
 
    return v;
}
 
string change10tok(int n, int k) // n을 k진수로
{
    string s = "";
 
    while (n != 0)
    {
        s.push_back((n % k) + '0');
        n /= k;
    }
 
    reverse(s.begin(), s.end());
 
    return s;
}
 
int solution(int n, int k) {
    int answer = 0;
 
    string temp1 = change10tok(n, k);
    vector<string> temp2 = divide(temp1);
 
    for (int i = 0; i < temp2.size(); i++)
    {
        if (temp2[i] == "") continue;
        if (checkPrimeNum(stoll(temp2[i]))) answer++;
    }
 
    return answer;
}

 

그냥 처음 딱 문제를 보면 풀기 싫어지긴 하는데, 사실 실상은 많이 어렵지 않은 문제긴 했다.

정확히 3가지의 기능을 구현할줄 알면 된다. 

 

1. 10진수를 n진법으로의 변환

2. 문자열을 특정 토큰으로 split하기

3. 소수판별

 

코테를 준비하는 사람이라면 어렵지않게 구현할 수 있을것이다.

주의할점 하나는 10진수 n을 k진법으로 변환할 때 숫자가 매우 길어질 수 있기때문에 long long으로 넉넉하게 잡아주자.

소수판별에서는 주어진 n에 대해서 반복문을 돌릴 때 n까지 할필요 없이 루트n까지만 돌려야 한다.

루트n 미만으로 하니까 14,16번에서 실패가 떠서 루트n 이하로 해주니까 해결됐다.