[프로그래머스/Level 2] k진수에서 소수 개수 구하기

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

프로그래머스

카카오 기출

 

입력받은 숫자 n을 k진수로 변환하는 것은 어렵지 않다. 그러나 주의해야 할 점이 두 가지 존재한다.

 

1. k진수로 변환된 수가 int의 범위를 벗어날 수 있다.

2. 단순히 2부터 k진수로 변환된 수 - 1 값을 하나씩 체크하며 소수 여부를 판단하면 TLE 발생할 수 있다.
(아마 1번 TC에서 TLE이 발생할 것이다.)

 

1번은 long long 타입을 사용함으로써 해결할 수 있고, 2번은 제곱근 수만큼만 비교하면 시간을 단축시켜 해결할 수 있다.

 

#include <string>
#include <vector>
#include <algorithm>
#include <sstream>
#include <iostream>
using namespace std;
typedef long long ll;

bool isPrime(string token) {
    if(token == "" || token == "1") return false;
    ll num = stoll(token);
    for(ll i = 2; i * i <= num; i++) {
        if(num % i == 0) return false;
    }
    return true;
}

string convert(int n, int k) {
    string num = "";
    while(1) {
        if(n == 0) break;
        num.insert(0, to_string(n % k));
        n /= k;
    }
    return num;
}

int solution(int n, int k) {
    int answer = 0;
    string num = convert(n, k);
    stringstream ss(num);
    string token;
    while(getline(ss, token, '0')) {
        if(isPrime(token)) answer++;
    }
    return answer;
}