k진수에서 소수 개수 구하기

조금 예전에 풀었던 문제인데 이제야 올려본다. 카카오에서 이번년도 유난히 코테를 쉽게 내준것만 같은 레벨2 문제다. k 진수로 숫자를 변형 시키고 해당 룰에 따라서 소수를 계속 확인해주면 되는 문제다.

#include <string>
#include <vector>
#include <bits/stdc++.h> 
using namespace std;

string change(int n, int k){
    string res = ""; 
    while(n){
        res += to_string(n % k); 
        n /= k; 
    }
    reverse(res.begin(),res.end()); 
    return res; 
}

bool checkPrime(string s){
    long tmp = stol(s); 
    if(tmp == 1 || tmp == 0) return false; 
    for(int i = 2; i <= sqrt(tmp); i++){
        if((tmp % i) == 0) return false; 
    }
    return true; 
}

int solution(int n, int k) {
    int answer = 0;
    int start = -1;
    string ss = change(n,k); 
    for(int i = 0; i < ss.length(); i++){
        if(ss[i] == '0'){
            string ins = ss.substr(start+1, i - (start+1)); 
            if(!ins.empty() && checkPrime(ins)){
                answer++; 
            }
            start = i; 
        }
    }
    if(start != ss.length()-1){
        if(checkPrime(ss.substr(start+1))){
            answer++; 
        }
    }
    return answer; 
}

여기에서 중요한거는 3가지이다.

1. K 진법으로 바꾸는 방법
2. 소수인지 확인 할 수 있는 함수
3. 투포인터식 접근

1번에서 언급한 K 진법으로 바꾸는 방법은

string change(int n, int k){
    string res = ""; 
    while(n){
        res += to_string(n % k); 
        n /= k; 
    }
    reverse(res.begin(),res.end()); 
    return res; 
}

위와 같은데. K 가 있고 바꿔야 할 숫자가 있을떄 숫자를 K 로 나누고 남는 수를 계속 string 형식으로 더해준뒤에, reverse 해주면 K 진법으로 바꾸기가 끝난다.

2번에서 언급한 소수인지 확인 할 수 있는 함수는

bool checkPrime(string s){
    long tmp = stol(s); 
    if(tmp == 1 || tmp == 0) return false; 
    for(int i = 2; i <= sqrt(tmp); i++){
        if((tmp % i) == 0) return false; 
    }
    return true; 
}

위와 같은데 1이나 0일 경우 소수가 아니기에 바로 리턴해준다. 이 문제에서는 소수의 크기가 크기 때문에 stol 을 사용해서 long 으로 바꾼것도 확인 할 수 있다. 후에는 2에서부터 특정 숫자까지 루프를 돌리면서 만약 stol 로 변환한 숫자가 루프에서 지정한 범위에 숫자에서 한번이라도 나뉘어지면 false 를 리턴해준다. 참고로 소수 판별시에는 sqrt() 를 쓰자. 단순히 tmp/2 로 했다가는 시간초과가 났었다.

3번에서 언급한 투포인터 접근은

int start = -1;
for(int i = 0; i < ss.length(); i++){
        if(ss[i] == '0'){
            string ins = ss.substr(start+1, i - (start+1)); 
            if(!ins.empty() && checkPrime(ins)){
                answer++; 
            }
            start = i; 
        }
    }
    if(start != ss.length()-1){
        if(checkPrime(ss.substr(start+1))){
            answer++; 
        }
    }
    return answer; 

위와 같은데 숫자 0을 발견한 순간 0 전에 있는 모든 숫자를 substring 으로 모은후에 소수 판별을 해주면 된다. 여기에서는 start 부터 0을 발견한 index - start + 1 을 해주어야지 알맞는 숫자로 substring 을 모을 수 있다. 그리고 소수를 확인 해주고 난 후에는 start 를 해당 0에 있었던 자리로 옮겨서 계속 투포인터 형식으로 탐색을 해주면 된다.

쉬운 문제가 맞긴한데 좀 기본기가 있어야 할거같다. 사실 소수랑 진법 변환을 까먹어서 인터넷 검색해봤다. 만약 인터넷 검색이 안되는 환경이었으면 나는 바로 나가리 였다.

배운점:
1. 진법 변환 함수
2. 소수 변환 함수