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

이번에는 다다음주 쯤있을 카카오 블라인트를 신경을 좀 써보고자 한번 시간을 재면서 풀었다.

웬걸 이딴 문제를 푸는데 1시간이 걸렸다!ㅋㅋ

아 시간을 들일 문제가 절대 아닌데 스스로에게 조금 실망했다.

단계를 나누어서 풀어서 시간이 쥰나 오래걸렸음에도 할 수 있었다. 첫째로, k진수로 바꾸어서 저장한다. 이 때, 0이 있는 위치를 파악하기 위해 배열에 한자리 한자리씩 저장하면서, 0의 위치는 따로 배열에 담았다. 

이 후 아까 저장한 0의 위치를 기준으로 숫자를 다 잘라서 또다른 배열에 저장하였다.

이제 이 배열을 순회하면서 이게 소수인지 아닌지를 판단해 주었다 끝!! 이상하게 0 기준으로 나누는데에서 시간을 드럽게 잡아먹었다. 멍청 그자체 ㅋㅋ

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

using namespace std;

int check_sosu(long long num)
{
    if (num < 2) return 1;
	int a = (int) sqrt(num);
	for (int i = 2; i <= a; i++) if (num % i == 0) return 1;
	return 0;
}
int solution(int n, int k) {
    int answer = -1;
    //일단 k진수로 바꾸기,
    //에라토스테네스 해야하는데 그 범위를...100만을 2진수로 바꾸면 배열로하기에 너무 사이즈가 커짐.
    //k진수로 바꾼다음에 처음으로 0이 등장할때까지의 수가 소수인지, 이후로 0 기준으로 계속 확인. -> 이건 어케 하노
    //에라토스 안하고 그냥 0을 기준으로 다 나눠서 숫자들만 벡터에 담아놓고 걔들만 소수인지 찾던가. --> 이거로 일단 나누자
    
    //1단계 : k진수로 바꾸기
    long long k_n = 0;
    vector <int> tmp;
    vector <int> tmp2;
    vector <int> z_idx;
    while(n > 0)
    {
        tmp.push_back(n%k);
        n/=k;
    }
    long long tmpsize= tmp.size();
    
    z_idx.push_back(0);
    for(int i = 0; i< tmpsize; i++)
    {
        if(tmp[tmpsize-i-1] == 0)
            z_idx.push_back(i);       //0이 위치한 위치를 기억함.
        tmp2.push_back(tmp[tmpsize-i-1]);
    }
    for(int i = tmp.size()-1; i >= 0; i--)
        k_n = k_n*10 + tmp[i];    
    //cout<<k_n<<'\n';
    z_idx.push_back(tmpsize);
    vector<long long> dividened;
    //2단계 : 0을 기준으로 나뉘는 수 다 저장하기.
    for(int i = 0; i< z_idx.size()-1; i++)
    {
        long long big = pow(10, tmp.size() - z_idx[i+1]);
        long long small = pow(10, z_idx[i+1] - z_idx[i]);
        long long ans1 = k_n / big;
        long long ans2 = ans1 % small;
        dividened.push_back(ans2);
    }
    // step3. 나눈애들이 소수인지 확인.
    for(int i = 0; i< dividened.size(); i++)
    {
        if (check_sosu(dividened[i]) == 0)
            answer++;
    }
    
    return answer+1;
}