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

문제 내용

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

k진수에서 소수 개수 구하기

문제의 유형 및 풀이 방법

단순 구현 문제이다.

먼저 10진수 n을 k진수 문자열로 변환한다. 아래는 k진수로의 변환 코드이다.

string ConvertDecimalToBaseK(int num, int k)
{
    int share = 0;
    int remainder = 0;
    int i = 0;
    string stringConverted = "";

    while (num >= k)
    {
        share = num / k;
        remainder = num % k;

        stringConverted.insert(0, to_string(remainder));
        num = share;
    }
    stringConverted.insert(0, to_string(share));

    return stringConverted;
}

그 다음, 구한 문자열을 "0"을 구분자(delimeter)로 split한다. 아래는 split 코드이다.

void split(string str, vector<string>& out, string delim)
{
    size_t start = 0;
    size_t end = 0;
    string substring = "";

    end = str.find(delim, start);
    while (string::npos != end)
    {
        // substr의 2번째 인자는 index가 아닌 substring의 길이인 것에 주의.
        substring = str.substr(start, end - start);
        // delim(0)이 여러 번 이어서 나오는 경우가 있어 이를 처리.
        // e.g. 3진수: "2101000020"
        if (0 < substring.length())
        {
            out.push_back(substring);
        }

        start = end + delim.length();
        end = str.find(delim, start);
    }
    // str의 맨 마지막에 delim이 있을 수 있어 이를 처리.
    // e.g. 3진수: "21010220"
    if (str.length() > start)
    {
        substring = str.substr(start, end);
        out.push_back(substring);
    }
}

split 결과인 out 벡터의 문자열들이 소수인지 판별하고, 소수이면 카운트한다. 아래는 소수를 판별하는 코드이다.

bool IsPrimeNumber(int64_t num)
{
    if (1 >= num)
    {
        return false;
    }

    for (int64_t i = 2; i <= sqrt(num); i++)
    {
        if (0 == num % i)
        {
            return false;
        }
    }

    return true;
}

복습해야할 내용

• int 자료형은 약 21억까지만 표현 가능하다.
  이를 초과하는 값이 사용될 경우 <cstdint>의 int64_t 자료형을 사용하자 (또는 long long int를 써도 됨). int64_t는 경이 넘어가는 범위의 정수도 담을 수 있다.
• 소수 판별 시에는 sqrt(num) 까지만 검사하기. sqrt(num)은 <cmath>에 있다.
• 자주 사용되는 <cmath> 함수들:
  • min(x, y) : x와 y 중 최솟값을 리턴한다.
  • max(x, y) : x와 y중 최댓값을 리턴한다.
  • ceil(x) : x를 올림한다. 리턴값은 double
  • floor(x) : x를 내림한다. 리턴값은 double
  • abs(x) , fabs(x) : x의 절댓값을 리턴한다. fabs(x)의 리턴값은 double
• std::string의 substr의 2번째 인자는 substring의 길이를 나타낸다. (index가 아닌 것에 주의.)
• std::string의 insert 함수를 이용하여 원하는 index 위치에 문자열을 삽입할 수 있다.
• e.g.) str.insert(0, "hello") : index 0 위치에 hello 문자열 삽입.

소스 코드

#include <string>
#include <vector>
#include <cmath>
#include <iostream>
#include <cstdint>

using namespace std;

string ConvertDecimalToBaseK(int num, int k)
{
    int share = 0;
    int remainder = 0;
    int i = 0;
    string stringConverted = "";

    while (num >= k)
    {
        share = num / k;
        remainder = num % k;

        stringConverted.insert(0, to_string(remainder));
        num = share;
    }
    stringConverted.insert(0, to_string(share));

    return stringConverted;
}

void split(string str, vector<string>& out, string delim)
{
    size_t start = 0;
    size_t end = 0;
    string substring = "";

    end = str.find(delim, start);
    while (string::npos != end)
    {
        // substr의 2번째 인자는 index가 아닌 substring의 길이인 것에 주의.
        substring = str.substr(start, end - start);
        // delim(0)이 여러 번 이어서 나오는 경우가 있어 이를 처리.
        // e.g. 3진수: "2101000020"
        if (0 < substring.length())
        {
            out.push_back(substring);
        }

        start = end + delim.length();
        end = str.find(delim, start);
    }
    // str의 맨 마지막에 delim이 있을 수 있어 이를 처리.
    // e.g. 3진수: "21010220"
    if (str.length() > start)
    {
        substring = str.substr(start, end);
        out.push_back(substring);
    }
}

bool IsPrimeNumber(int64_t num)
{
    if (1 >= num)
    {
        return false;
    }

    for (int64_t i = 2; i <= sqrt(num); i++)
    {
        if (0 == num % i)
        {
            return false;
        }
    }

    return true;
}

int solution(int n, int k)
{
    int answer = 0;
    string numString = "";
    vector<string> numList;

    // 양의 정수 n을 k진수 numString로 변환한다.
    numString = ConvertDecimalToBaseK(n, k);

    // 변환한 숫자 문자열을 0을 delimeter로 split한다.
    split(numString, numList, "0");

    // split한 숫자들 중에서 소수의 개수를 구한다.
    for (string s : numList)
    {
        int64_t target = stoll(s);

        if (1 == target)
        {
            continue;
        }

        if (true == IsPrimeNumber(target))
        {
            answer++;
        }
    }

    return answer;
}