[Programmers] Lv2. k진수에서 소수 개수 구하기 | C++

🔗문제 보러가기

프로그래머스

 

👨‍💻풀이 과정

 

소수 판별 부분에서 int 오버플로우가 날 수 있으므로, long long 자료형으로 작성하였습니다. 저 부분 때문에 20분은 소모한 듯해요...

 

1. n을 k진수로 바꾸어, 문자열로 저장하기

2. k진수 문자열에서 '0'을 기준으로 문자열 분리하기

3. 각 분리된 문자열들을 소수 검사하기

 

✏️소스 코드 및 결과

#include <vector>
#include <string>
#include <sstream>
#include <algorithm>
using namespace std;

string GetKNumber(int n, int k) {
    string number;

    while (true) {
        int quotient = n / k;
        int remainder = n % k;
        number.push_back(remainder + '0');
        
        if (quotient == 0)
            break;
        n = quotient;
    }

    reverse(number.begin(), number.end());
    return number;
}

bool IsPrimeNumber(long long n) {
    if (n == 1)
        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 kNum = GetKNumber(n, k);
    stringstream tokenizer(kNum);
    string num;

    while (getline(tokenizer, num, '0')) {
        if (!num.empty())
            answer += IsPrimeNumber(stoll(num));
    }

    return answer;
}