[프로그래머스 lv2] k진수에서 소수 개수 구하기 풀이

해설

문제의 요지는 0으로 둘러쌓인 숫자 중 소수인 수를 카운트 하라는 것이다.

 

수 n을 k진수로 변환하여 문자열로 저장한다.

'0'이 나올 때까지 수를 계산하여 tmp에 저장하고, '0'이 나오면, 지금까지 계산해놓은 수가 소수인지 판단하여 카운트를 1 증가 시킨다.

문자열이 끝날 때까지 해당 작업을 반복한 후 카운트를 리턴하면 된다.

 

전체 코드

#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <tuple>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <climits>
#include <set>
#include <unordered_set>
#include <map>
#include <unordered_map>
#include <string>
#include <sstream>
#include <iostream>

using namespace std;
using ii = pair<int, int>;
using iii = tuple<int, int, int>;

#define X first
#define Y second

bool isPrime(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) {
    
    //수 n을 k진수로 변환하여 문자열 s에 저장
    string s = "0";
    while (n) {
        s += n%k+'0';
        n /= k;
    }
    reverse(s.begin(), s.end());
    
    //0으로 둘러쌓인 숫자가 소수인지 확인하여 카운트
    int cnt = 0;
    long long tmp = 0;
    for (auto c : s) {
        if (c != '0') tmp = tmp*10+c-'0';
        else {
            if (isPrime(tmp)) cnt++;
            tmp = 0;
        }
    }
    return cnt;
}