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

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

문제 링크

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

분석

숫자 n을 k진수로 변환해주어야 합니다.

특정 조건의 소수는 0을 기준으로 숫자가 분리됩니다.
예를 들어, 437674을 3진수로 바꾸면 211020101011입니다.
변환된 수에서 0을 기준으로 분리된 수가 소수인지 확인하면 된다는 것을 알 수 있습니다.

풀이

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

// 소수인지 확인하는 함수
bool isPrimeNumber(long long num)
{
    if (num < 2)
    {
        return false;
    }
    
    // 소수인지 반복문으로 확인
    for (long long i = 2; i * i <= num; ++i)
    {
        if (num % i == 0)
        {
            return false;
        }
    }
    
    return true;
}

int solution(int n, int k) {
    int answer = 0;
    
    // n을 k진수로 변환
    string convertNum = "";
    while (n > 0)
    {
        convertNum += to_string(n % k);
        n /= k;
    }
    reverse(convertNum.begin(), convertNum.end());
    
    string temp = ""; // 0을 기준으로 숫자를 분리한 문자열을 저장

    // 변환된 수를 순회
    for (char c : convertNum)
    {
        // 현재 글자가 0일 경우
        if (c == '0')
        {
            // 분리된 문자열이 비어있지 않고, 소수인 경우
            if (!temp.empty() && isPrimeNumber(stoll(temp)))
            {
                ++answer;
            }
            
            // 문자열을 초기화
            temp = "";
        }
        else
        {
            // 현재 글자가 0이 아니므로 문자열에 저장
            temp += c;
        }
    }
    
    // 마지막 숫자 확인
    if (!temp.empty() && isPrimeNumber(stoll(temp)))
    {
        ++answer;
    }
    
    return answer;
}

reverse(convertNum.begin(), convertNum.end())를 해주는 이유는 진법 변환 과정에서 숫자의 자릿수가 거꾸로 저장되기 때문입니다.
예를 들어, 437674을 3진수로 바꾸면 211020101011를 만들어주어야 하지만, 위의 방법대로 변환 시 110101020112가 나오기 때문에 자릿수를 뒤집어주어야 합니다.

isPrimeNumber함수의 반복문에서 종료 조건은 i <= sqrt(num)을 사용 할 수 있습니다.
i * i <= num의 경우 i * i가 int일 경우 오버플로우가 발생 할 수 있으므로, long long을 사용해주어야 합니다.

마지막 숫자를 별도로 확인하는 이유는 변환한 수의 마지막에는 0이 없어 확인을 1번 적게하기 때문입니다.

성능 요약

시간 복잡도는 $O(log \ n \times \sqrt{m})$

• n을 k진수로 변환하는 반복문 $O(log \ n)$
• 문자열을 뒤집는 reverse함수 $O(log \ n)$
• convertNum을 순회하는 반복문 $O(log \ n)$
• stoll함수 $O(log \ n)$
• 소수인지 확인하는 함수 $O(\sqrt{m})$
• $O(log \ n + log \ n + log \ n + log \ n \times \sqrt{m})$

공간 복잡도는 $O(log \ n)$입니다.

• 변환된 수를 저장하는 문자열 convertNum $O(log \ n)$
• 0을 기준으로 분리된 숫자를 저장하는 문자열 temp $O(log \ n)$
• $O(log \ n + log \ n)$

테스트 1 〉 통과 (8.10ms, 4.2MB)
테스트 2 〉 통과 (0.01ms, 4.14MB)
테스트 3 〉 통과 (0.02ms, 4.15MB)
테스트 4 〉 통과 (0.01ms, 4.13MB)
테스트 5 〉 통과 (0.03ms, 3.75MB)
테스트 6 〉 통과 (0.02ms, 4.17MB)
테스트 7 〉 통과 (0.02ms, 4.13MB)
테스트 8 〉 통과 (0.02ms, 4.21MB)
테스트 9 〉 통과 (0.02ms, 4.14MB)
테스트 10 〉 통과 (0.02ms, 4.13MB)
테스트 11 〉 통과 (0.01ms, 4.2MB)
테스트 12 〉 통과 (0.01ms, 4.14MB)
테스트 13 〉 통과 (0.03ms, 4.07MB)
테스트 14 〉 통과 (0.01ms, 4.21MB)
테스트 15 〉 통과 (0.01ms, 4.21MB)
테스트 16 〉 통과 (0.01ms, 4.14MB)