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

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

프로그래머스

고민했던 부분  

    1. 소수 미리 구하기 - 에라토스테네스의 체 , 길이 몇 까지?
    2. 그때 그때 소수 체크
    3. 1,2섞어서

=> 1번으로 하려다가 몇 번째 숫자까지 구할지 애매하고 그때 그때 소수인지 체크하는 것이 더 빠를 것 같아서 2번으로 했다.
    
 1. 숫자로 만들어서 string? 바로 string?
 처음에 string을 활용해서 k진수를 구하고  숫자 부분만 소수인지 판별하려고 했다.
이때 k 진수를 만들고 숫자를 추출할지 만드는 과정에서 숫자가 있으면 판별할지 고민했다. 2번으로 하려고 했는데 
k진수를 구할 때 뒤에서부터 구해지고(ex) 34056이 있으면 6->5->0->4->3순서로 구해짐) 그걸 다시 숫자로 바꿔서 판별할 필요가 없다는 생각이 들었다.
그래서 문자열로 바꾸지 않고 바로 숫자를 k 진수(long long)로 변환 해 주었다.

풀이

k진수에서 소수가 나올 수 있는 경우는 다음 4가지
1. 0P0 가운데 가능
2. P0 시작 가능
3. 0P 끝날 때 가능
4. p 0이 없을때 가능

1. n을 k 진수로 변환한다. 자릿수가 낮은 수부터 구해진다.
2. 처음 자릿수가 숫자이고 그 뒤에 0이 등장한다면 3번째 경우가 가능하므로 소수인지 판별한다.
3. 0이 등장한 후로 num이 1보다 커지고 다시 0이 등장하면 1번째 경우가 가능하므로 소수인지 판별한다.
4. while 문이 종료 한 뒤에 num이 0보다 크다는 것은 2번 케이스이거나 4번 케이스이므로 소수인지 판별한다.

주의해야 할 점 & 틀렸던 부분
1.소수 인지 판별할 때 num>0이라는 조건을 했었는데 그러면 num이 1일때도 소수라고 판별이 된다.
   num>=2로 바꾸어 주었다.
2.num이 int형을 넘어갈 수 있으므로 long long으로 바꿔주었다.
3. 그래도 1번 케이스에서 시간초과가 났었다.
소수인지 판별할때 판별할 수의 제곱근까지만 나눠보면 된다. 나는 판별할 수의 절반까지 나누어서 시간 초과가 났었다.
예전에 이부분 공부한 적이 있었는데 최근 문제는 에라토스테네스의 체 사용하고 절반까지 나눠도 시간초과가 안났었기 때문에 까먹었다.
ex) 36이 소수인지 판별하려면 2,4,6까지만 나누어 보면 된다. 2x18=36, 4x9=36 이기때문에 굳이 9와,18로 나누어볼 필요가 없다.

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

//1. 0P0 가운데 가능
//2. P0 시작 가능
//3. 0P 끝날 때 가능
//4. p 0이 없을때 가능
bool isPrimeNum(long long t)
{
    //제곱근 까지만 검사
    int tt=sqrt(t);
    for(long long i=2;i<=tt;i++)
    {
      
        if(!(t%i))
        {
            t=0;
            return false;
        }
        
    }
           
     return true;            
}

int solution(int n, int k) {
    int answer = 0;
    
    bool mid=false;
    bool chk=false;
    long long num=0;
    long long idx=1;
    while(n>0)
    {
        if(n%k)//나머지가 있을때
        { 
            num+=(idx*(n%k));
            idx*=10;
            chk=true;
        }
        else 
        {
            idx=1;
            if(chk&&mid)//중간  
            {
                if(num>=2)
                {
                //소수인지 판별
                    if(isPrimeNum(num))
                    {
                        answer++;
                    }
                    
                }
            }
            else if (chk)//끝 
            {
                
                if(num>=2)
                {
                //소수인지 판별
                if(isPrimeNum(num))
                {
                 
                    answer++;
                
                }           
                    
                }
            }
            mid=true;
           
            num=0;
            
        }
        n/=k;
    }
    if(num>=2)//처음 and 0없는경우
    {
       //소수인지 판별
        if(isPrimeNum(num))
        {
            answer++;
        }
    }
    
  
    return answer;
}