[Programmers] 카카오 블라인드 2022 - k진수에서 소수 개수 구하기

카카오 블라인드 2021 - k진수에서 소수 개수 구하기

---

Kakao Blind Recruit 2022 - k진수에서 소수 개수 구하기

문제 Comment

문제를 보면 뭔가 조건이 많습니다. 근데 잘 보면 조건은 1개만 확인하면 충분히 풀리는 문제입니다.

특별히 코멘트를 할 내용은 없습니다. 바로 들어가봅시다.

---

문제 풀이

문제에서 소수와 관련된 판별힌트를 주고 있습니다.

• 0P0처럼 소수 양쪽에 0이 있는 경우
• P0처럼 소수 오른쪽에만 0이 있고 왼쪽에는 아무것도 없는 경우
• 0P처럼 소수 왼쪽에만 0이 있고 오른쪽에는 아무것도 없는 경우
• P처럼 소수 양쪽에 아무것도 없는 경우
• 단, P는 각 자릿수에 0을 포함하지 않는 소수입니다.
  예를 들어, 101은 P가 될 수 없습니다.

예를 든 것을 보면 437674를 3진수로 표현한 211020101011애서 위의 조건에 해당하는건 211, 2, 11인데 211은 P0, 2는 0P0, 11은 0P라고 설명하고 있습니다.
근데 조금 뭔가 이상하지 않나요? 과연 조건이 저렇게 4개일 이유가 있을까요?
사실 소수를 판별하는 조건은 딱 1개입니다. 이전의 0이 나온 후로 0이 나왔을때까지 취합된 숫자가 소수인지 아닌지만 판별하면 끝입니다. 결국 위에서 제시한 조건은 0을 기준으로 끊은 수가 소수인가? 입니다.

이제 조건을 파악했으니 구현을 해봅시다.

---

코드

#include <string>
#include <vector>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <cmath>
using namespace std;

typedef long long ll;

bool isPrime(ll num) {
    if (num == 1) return false;
    if (num == 2) return true;
    
    ll lim = sqrt(num);
    
    for (ll i = 2; i <= lim; i++) {
        if (num % i == 0) return false;
    }
    
    return true;
}

string changeNumber(int num, int k) {
    string ret = "";
    int rem = 0;
    
    while(num != 0) {
        rem = num % k;
        num /= k;
        
        ret += to_string(rem);
    }
    
    reverse(ret.begin(), ret.end());
    
    return ret;
}

int solution(int n, int k) {
    int answer = 0;
    string number = "";
    
    if (k == 10) number = to_string(n);
    else number = changeNumber(n, k);
    
    string tmp = "";
    char curr = '\0';
    
    for (int i = 0; i < number.size(); i++) {
        curr = number[i];
        
        if (curr == '0') {
            if (tmp == "") continue;
            if (isPrime(stoll(tmp))) answer++;
            
            tmp = "";
        }else tmp += curr;

    }
    
    if (tmp != "") {
        if (isPrime(stoll(tmp))) answer++;
    }
    
    return answer;
}

소수판별시에 에라토스테네스의 체를 쓰시는 경우가 있는데 이 경우 segmentation fault 오류가 발생합니다.
근데 제 기억으론 당시에 제가 에라토스를 쓴걸로 기억하는데 왜 안되는지는 모르겠네요…..
단순 소수 판별 써도 괜찮습니다. 물론 소수판별시 좀 더 시간을 줄이고자 제곱근까지만 체크하는 것이 가장 좋습니다.
또한 워낙 값이 큰 경우가 나올 수 있으므로 자료형에도 주의해야합니다.