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

문제

---

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

풀이

---

10진수를 n진수로 변환하고, 소수인지 판별하고, 숫자 앞 뒤에 0이 있는지 확인하여 이를 모두 충족하는 경우를 찾는 문제이다. 소수 판별에는 시간이 많이 걸리므로, 숫자 앞 뒤 0이 존재하는 지를 먼저 판단하여, 시간이 오래 걸리는 작업은 최소화한다. 그리고 조건으로 1,000,000까지 라는 조건이 붙었으므로 long long을 사용하여 계산한다.

#include <string>
#include <vector>
#include <stack>
#include <algorithm>
#include <cmath>

using namespace std;

bool isPrime(long long number)
{
    for (long long i = 2; i <= sqrt(number); i++)
    {
        if (number % i == 0) 
        {
            return false;
        }
    }

    return true;
}


long long solution(int n, int k)
{
    long long answer = 0;

    stack<long long> ConvertNum;

    while (n != 0)
    {
        bool isDivide = false;

        for (long long i = k - 1; i >= 1; i--)
        {
            if (n % k == i)
            {
                ConvertNum.push(i);
                isDivide = true;
                break;
            }
        }

        if (!isDivide)
        {
            ConvertNum.push(0);
        }

        n /= k; 	
    }

    long long temp = 0;
    long long size = ConvertNum.size();

    for (long long i = 0; i < size; i++)
    {
        if (ConvertNum.top() != 0)
        {
            temp *= 10;
            temp += ConvertNum.top();
            ConvertNum.pop();
        }

        else
        {
            if (temp != 0)
            {
                if (isPrime(temp) == true && temp != 1)
                {
                    answer++;
                }
            }

            temp = 0;
            ConvertNum.pop();

        }
    }

    if (temp != 0)
    {
        if (isPrime(temp) == true && temp != 1)
        {
            answer++;
        }
    }


    return answer;
}