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

프로그래머스 k진수에서 소수 개수 구하기 [2022 KAKAO BLIND RECRUITMENT]
https://programmers.co.kr/learn/courses/30/lessons/92335

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

 

문제 풀이

• 세 단계를 거쳐 문제 해결
  1. 10진수 숫자인 n을 k 진수로 변환 (※ 10진수를 k 진수로 바꾸면 매우 길어질 수 있기 때문에 long long 사용)
  2. 변환한 숫자를 0을 기준으로 parsing
  3. parsing 된 각 숫자들이 소수인지 아닌지 판별

코드

#include <string>
#include <cmath>

using namespace std;

typedef long long ll;

bool prime(ll n) { // 소수 판별
    if(n < 2) return false;
        
    for(int i=2; i<=sqrt(n); ++i) {
        if(n % i == 0) return false;
    }
    
    return true;
}

string convert_num(int n, int k) { // k진수로 변환
    string ret = "";
    
    while(n) {
        ret += to_string(n % k);
        n /= k;
    }
    
    return string(ret.rbegin(), ret.rend());
}

int get_answer(string num) { // 0을 기준으로 parsing하여 소수이면 count
    string tmp = "";
    int ret = 0;
    
    for(int i=0; i<num.length(); ++i) {
        if(num[i] == '0' && !tmp.empty()) {
            ll n = stoll(tmp);
            if(prime(n)) ret++;
            tmp = "";
        }
        else tmp += num[i];
    }
    
    if(!tmp.empty()) {
        ll n = stoll(tmp);
        if(prime(n)) ret++;
    }
    
    return ret;
}

int solution(int n, int k) {
    int answer = 0;
    
    string num = convert_num(n, k);
    
    return get_answer(num);
}

실행 결과