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

해결 언어: C++

1. 문제 파악

문제는 다음으로 요약할 수 있다.

1. n을 k진수로 변환
2. 0을 기준으로 숫자를 나누기
3. 숫자가 소수인지 판별하여 카운트

여기서 주의해야 할 부분은 k진수로 변환한 숫자이 크기가 너무 크다는 점이다. int 대신 long long, string으로 저장하여 사용해야 overflow를 방지할 수 있다.

2. 알고리즘 선택

1. n을 k진수로 변환
   간단히 나누기와 나머지 연산으로 변환할 수 있다.

while (n) {
        int remain = n % k;
        str_number = to_string(remain) + str_number;
        n /= k;
    }

2. 0을 기준으로 숫자를 나누기
   숫자를 문자열로 저장했으니 find 함수로 0을 찾아 저장했다.

    size_t start = 0;
    size_t end;
    
    while ((end = str_number.find('0', start)) != string::npos) {
        string spliced_str_number = str_number.substr(start, end - start);
        if (!spliced_str_number.empty()) {
            numbers.push_back(stoll(spliced_str_number));
        }

        start = end + 1;
    }
    

    string spliced_str_number = str_number.substr(start);
    if (!spliced_str_number.empty()) {
        numbers.push_back(stoll(spliced_str_number));
    }

C++에는 split 함수가 없어 다른 언어와 비교해 길어졌다.
if (!spliced_str_number.empty())를 사용한 이유는 문자열에 "00"이 들어가있다면 substr과정에서 빈 문자열을 리턴하니 예외처리를 해줬다.

3. 숫자가 소수인지 판별하여 카운트
   소수 판별은 에라토스테네스의 체와 2부터 √숫자까지 나머지 연산으로 판단할 수 있다.
   여러개 판별해야 하니 에라토스테네스의 체를 사용하고 싶지만 숫자가 너무 크므로 후자를 선택했다.

	int countPrime = 0;
    
    for (auto n : numbers) {
        if (n < 2) {
            continue;
        }
        
        bool is_prime = true;
        
        for (long long i = 2; i*i < n+1; i++) {
            if (n % i == 0) {
                is_prime = false;
                break;
            }
        }
        
        if (is_prime) {
            countPrime++;
        }
    }

1은 예외처리 if문으로 예외처리
2와 3은 반복문을 들어가지 않으니 따로 처리할 필요가 없다.

3. 최종코드

#include <string>
#include <vector>
using namespace std;

int solution(int n, int k) {
    string str_number = "";
    vector<long long> numbers;
    
    while (n) {
        int remain = n % k;
        str_number = to_string(remain) + str_number;
        n /= k;
    }

    size_t start = 0;
    size_t end;
    
    while ((end = str_number.find('0', start)) != string::npos) {
        string spliced_str_number = str_number.substr(start, end - start);
        if (!spliced_str_number.empty()) {
            numbers.push_back(stoll(spliced_str_number));
        }

        start = end + 1;
    }
    

    string spliced_str_number = str_number.substr(start);
    if (!spliced_str_number.empty()) {
        numbers.push_back(stoll(spliced_str_number));
    }


    
    int countPrime = 0;
    
    for (auto n : numbers) {
        if (n < 2) {
            continue;
        }
        
        bool is_prime = true;
        
        for (long long i = 2; i*i < n+1; i++) {
            if (n % i == 0) {
                is_prime = false;
                break;
            }
        }
        
        if (is_prime) {
            countPrime++;
        }
    }
    
    return countPrime;
}

4. 다른 사람의 풀이

'0'을 찾고 문자열 자르는 방법 대신, 한 글자씩 읽어 임시변수에 저장하고 '0'이면 임시변수를 소수판별하는 좀 더 효율적인 방식이 있었다.