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

문제 설명

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

제한사항

• 1 ≤ n ≤ 1,000,000
• 3 ≤ k ≤ 10

---

풀이

30분
주어진 숫자를 k진수로 변환하고, 문자열을 ‘0’을 delimiter로 나눈 후, 그 문자열이 10진수로 소수인지 판별하는 문제였다.
제출후 1번 케이스에서

signal: aborted (core dumped)

에러가 발생해서 원인을 찾는데 대부분의 시간을 사용했다.
문제의 제약조건을 통해 숫자가 가장 큰 경우를 생각해보면 1000000에 가까운 숫자를 3진법으로 나타냈을 때, 0이 나타나지 않은 경우 가장 큰 숫자가 나올 수 있다. 3^12 이 50만에 가까우므로, 12자리 숫자를 생각해보면 int 형의 표현범위(약 21억)를 넘게되어 에러가 발생했던 것이다.
그래서 string을 int가 아닌 long long으로 변환하여 판별하는 방식으로 바꾸어 해결하였다.

코드

// 03:24 ~ 03:52
#include <string>
#include <vector>
#include <cmath>

using namespace std;

string kdigit_transfer(int n, int k){
    string s = "";
    while(n > 0){
        s = to_string(n % k) + s;
        n /= k;
    }
    return s;
}

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

int solution(int n, int k) {
    int answer = 0;
    string s = kdigit_transfer(n,k);
    vector<string> v;
    for(int i =0; i < s.size(); ++i){
        if(s[i] != '0'){
            int j = 1;
            while(i + j < s.size() && s[i + j] != '0') ++j;
            v.push_back(s.substr(i,j));
            i += j - 1;
        }
    }
    for(string item : v){
        if(isprime(stol(item))) answer += 1;
    }
    return answer;
}