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

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

프로그래머스

---

문제 설명

양의 정수 n을 k진수로 바꿨을 대, 아래 조건에 맞는 소수가 몇개인지 확인하시오.

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

예를들어 437674는 3진수로 211020101011 으로 소수는 총 3개입니다.

제한조건

1 <= n <= 1,000,000

3 <= k <= 10

---

아이디어

1. 먼저 n을 k진수로 표현한 문자열로 바꿉니다.
2. 앞에서부터 0을 만날때까지 읽고, 0을 만나면 벡터에 기록하고 다음칸에서 시작합니다.  O(N)
(P0, 0P0, 0P가 확인 가능하고, P려면 전체가 0이 없어야하니 4가지 모두 체크 가능)
3.  벡터에 모든 수가 소수인지 체크합니다.  벡터 전체 확인O(N), 소수 확인O(logN)

 

---

코드

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

using namespace std;

bool isDecimal(unsigned long long x)
{
    if(x == 1) return false;
    if(x == 2) return true;
    if(x == 3) return true;
    
    for(unsigned long int i=2; i<sqrt(x)+1; i++)
    {
        if(x%i == 0){
            return false;
        }
    }
    return true;
}

int solution(int n, int k) {
    int answer = 0;
    string number = "";
    
    //K진수로 변환
    while(n > 0){
        number  =  to_string(n%k) + number;
        n /= k;
    }
    
    bool noZero = true;
    //0과 0사이를 돌아다니며 체크. 0P0, P0, 0P체크 가능
    vector<string> partition;
    string tmp = "";
    for(auto n : number)
    {
        if(n == '0'){
            if(tmp != ""){
                partition.push_back(tmp);
                tmp = "";
            }
            noZero = false;
        }
        else{
            tmp += n;
        }
    }
    if(tmp != "") partition.push_back(tmp);
    
    for(auto part : partition){
        if(isDecimal(stoull(part))) answer++;
    }
    
    return answer;
}