[Lv 2] k진수에서 소수 개수 구하기

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

프로그래머스

 

이 문제는 n진수를 만들고 진수에 해당하는 값이 소수인지 순차적으로 확인하는 문제이다.

 

먼저 n진수를 만드는 함수(calc)는 다음과 같다.

1. 빈 문자열을 생성

2. 변환시킬 숫자가 k보다 클 경우 빈 문자열에 n과 k를 나눈 나머지를 누적한다. 이후 n과 k를 나눠 n에 저장한다.

3. n이 0보다 큰경우 temp에 값을 누적시킨다.

4. 변환된 k진수의 값은 뒤집어져있으므로 reverse함수를 통해 원하는 형태로 바꾼다.

 

소수인지 확인하는 함수는 다음과 같다.

1. 소수인지 확인하는 값은 k진수의 값이기 때문에 long long 자료형을 사용하여 변수에 저장

2. 변환할 값이 2 미만인 경우 소수가 아니기 때문에 false 반환

3. 확인할 값이 소수인지 빠르게 확인하기 위해 sqrt(num) 범위로 확인

4. 확인할 값이 범위 안에서 나누어 떨어질 경우 소수가 아님

5. 모든 값을 확인 한 후 소수로 판정

 

문제의 조건에 맞는 소수를 찾는 방법은 다음과 같다.

1. 변환시킨 k진수의 값을 0번째 인덱스부터 확인

2. 현재 확인할 인덱스의 값이 '0'인 경우 누적시킨 문자열이 비어있지 않고 소수인 경우 answer수 증가

3. '0'이 아니면 빈문자열에 값 누적

 

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

string calc(int n, int k){
    
    string temp = "";
    while(n >= k){
        temp += to_string(n % k);
        n /= k;
    }
    if(n > 0)
        temp += to_string(n);
    
    reverse(temp.begin(),temp.end());
    return temp;
}
bool isPrime(string str){
    long long num = stoll(str);
    
    if(num < 2) return false;
        
    for(int i=2; i<=sqrt(num); i++) {
        if(num % i == 0) 
            return false;
    }
    return true;
}
int solution(int n, int k) {
    int answer = 0;
    
    string calcNum = calc(n, k);
    string temp = "";
    for(int i = 0;i<calcNum.length();i++){
        char c = calcNum[i];
        if(c == '0'){
            if(!temp.empty()&&isPrime(temp)){
                answer++;
            }
            temp = "";
        }
        else
            temp += c;
    }
    if(!temp.empty()&&isPrime(temp))
        answer++;
    
    return answer;
}