[2022 Kakao blind recruitment] k진수에서 소수개수 구하기

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

코딩테스트 연습 - k진수에서 소수 개수 구하기

[풀이방법]

1. 진법 변환

2. 0을 기준으로 자른다.

3. 자른 수가 소수인지 판별한다.

4. 소수라면 answer++

 

* 주의해야 할 점 : n 의 최대가 1,000,000 이고 3진법으로 변환할 경우 long long 이라도 수를 다 커버하지 못한다.

따라서, string 에 담아둔 후 문자열을 0을 기준으로 자른다.

stoi() 가 아닌 stoll()을 사용하여 string 을 long long 으로 변환하여 소수인지 확인한다.

#include <string>
#include <vector>

using namespace std;

string convert(int n, int k) {
    string res = "";
    string reverse = "";
    while(n != 0) {
        res += to_string(n%k);
        n /= k;
    }
    for(int i=res.size()-1; i>=0 ; i--)
        reverse += res[i];
    
    return reverse;
}

bool isPrime(long long n) {
    if(n < 2) 
        return false;
    
    for(long long i=2; i*i <= n; i++) {
        if(n % i == 0) 
            return false;
    }
    return true;
}


int solution(int n, int k) {
    int answer = 0;
    
    string str_n = convert(n, k);

    string tmp = "";
    for(int i=0; i<=str_n.size(); i++) {
        if(i == str_n.size() || str_n[i] == '0') {
            if(tmp!="" && isPrime(stoll(tmp))) 
                answer++;
            tmp = "";
        }
        else
            tmp += str_n[i];
    }
    return answer;
}