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

프로그래머스

숫자 N과 진수 K를 입력 받습니다. 10진수인 N을 K진수로 변환했을 때,

아래 조건에 맞는 소수의 개수를 찾아주세요 

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

 

풀이 방법

해당 문제에서 해결 해야하는 것은

1. N을 K진수로 변환하기

2. 0 사이의 숫자 찾기

3. 해당 숫자가 소수인지 확인하기

 

1번은 아래 코드로 해결이 가능합니다.

string convert(int n, int k)
{
    string ret;
    while (n > 0)
    {
        ret = to_string(n % k) + ret;
        n /= k;
    }
    return ret;
}

 

2번의 경우 '0'의 위치값을 오름차순으로 모아둔 후 해당 위치값을 이용해서 0 사이에 있는 수를 구해줍니다.

for (int i = 0; i < number.size(); i++)
    if (number[i] == '0')
        zeros.push_back(i);  

int prev = -1;
for (int i = 0; i <= zeros.size(); i++)
{        
    int idx = i < zeros.size() ? idx = zeros[i] : 0;
    string num = "";

	// P0 찾기
    if (prev == -1 && prev >= 0)
        num = number.substr(0, idx);

	// 0P 찾기
    else if (i == zeros.size())
        num = number.substr(prev+1, number.size() - (prev+1));

	// 0P0 찾기
    else
        num = number.substr(prev+1, idx-(prev+1));

    if (isPrime(num))
        answer++;

    prev = idx;
}

 

 

3번 소수인지 확인하는 방법입니다. 소수 체크는 제곱근까지만 확인해도 소수인지 아닌지 확인이 가능합니다.

bool isPrime(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;
}

 

정답 코드

#include <string>
#include <vector>
#include <iostream>

using namespace std;

string convert(int n, int k)
{
    string ret;
    while (n > 0)
    {
        ret = to_string(n % k) + ret;
        n /= k;
    }
    return ret;
}

bool isPrime(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;
}

bool isPrime(string num)
{
    long long ret = 0;
    for (int i = 0; i < num.size(); i++)
    {
        ret *= 10;
        ret += num[i] - '0';
    }

    return isPrime(ret);
}

int solution(int n, int k) 
{
    vector<int> zeros;
    
    string number = convert(n, k);

    for (int i = 0; i < number.size(); i++)
        if (number[i] == '0')
            zeros.push_back(i);  
    
    int answer = 0;
    int prev = -1;
    
    for (int i = 0; i <= zeros.size(); i++)
    {        
        int idx = i < zeros.size() ? idx = zeros[i] : 0;
        
        string num = "";
        
        if (prev == -1 && prev >= 0)
            num = number.substr(0, idx);
        
        else if (i == zeros.size())
            num = number.substr(prev+1, number.size() - (prev+1));
        
        else
            num = number.substr(prev+1, idx-(prev+1));
        
        if (isPrime(num))
            answer++;
        
        prev = idx;
    }
    
    
    return answer;
}