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

문제

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

프로그래머스

문자열을 숫자로 변환하고 소수인지 판별하는 문제였다.

 

문제 풀이

먼저 10진수로 주어진 n을 k진수로 변환해준 후(문자열), 각 수를 0을 단위로 끊어서 벡터에 저장했다(long long). 그리고 벡터에 저장된 수가 소수인지 판별했다.

 

굉장히 긴 수가 나올 수 있기 때문에 long long 타입을 사용했고, 소수를 판별하는 것도 처음에는 num/2 까지만 계산하게 했으나 시간 초과가 나와서 sqrt 함수를 사용해 제곱근까지 계산하도록 수정했다.

 

이것저것 할 일도 많고 이런저런 일도 있어서 굉장히 오랜만에 문제를 풀었는데 다시 열심히 풀어야겠다..!

#include <string>
#include <vector>
#include <stdlib.h>
#include <iostream>
#include <math.h>

using namespace std;

string knum="";

long long makeTenToK(int n, int k){ //k진수로 바꾸기
    long long result = 0;
    long long i=1;
    
    while(n>0){
        result += (i*(n%k));
        knum+= '0'+(n%k);
        n/=k;
        i*=10;        
    }
    
    return result;
}

int solution(int n, int k) {
    int answer = 0;
    long long result;
    
    //10진수 n을 k진수로 변환
    result = makeTenToK(n,k);
    
    //변환한 값에서 0이 포함되지 않은 소수 찾기 -> 0으로 자르기

    int ksize = knum.length();
    vector<long long> nums;
    long long num=0;
    for(int i=ksize-1;i>=0;i--){
        if(i == 0){ //마지막
            if(knum[i] !='0'){
                num*=10;
                num+=(knum[i]-'0'); 
                nums.push_back(num);                
            }
        }
        if(knum[i] == '0'){                
            nums.push_back(num);
            num = 0;
        }
        else{
            num*=10;
            num+=(knum[i]-'0');            
        }
    }        
    
    int flag = 0;
    //소수 판별
    for(long long i=0;i<nums.size();i++){
        flag = 0;
        long long checkNum = nums[i];

        if(checkNum == 0 || checkNum == 1) continue;
        for(long long j=2;j<=(sqrt(checkNum));j++){
            if(checkNum%j ==0){
                flag = 1;
                break;
            }
        }
        if(flag == 0) answer++;
        
    }
    
    
    return answer;
}