[C++] 프로그래머스 - k진수에서 소수개수 구하기 (Lv.2)

문제 설명

k진수에서 소수 개수 구하기 문제 설명

 

아이디어

0P0, P0, 0P, P 에 관한 설명들 모두 진법 변환 후 0을 기준으로 split 하라는 말이다.

그래서 

1. 진법 변환
2. 0을 기준으로 split 해 배열에 담음
3. 배열에 담은 것들을 소수인지 아닌지 판단해, 소수일 경우 answer+1 진행

순으로 코드를 짰다.

 

코드

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

using namespace std;

bool isPrime(long long n) {
    if(n==0 || n==1) return false;
    for(int i=2; i<=sqrt(n); i++){
        if(n%i == 0)
            return false;
    }
    return true;
}

int solution(int n, int k) {
    int answer = 0;
    string st;
    
    // 진법 변환
    while(n>0) {
        st += to_string(n%k);
        n /= k;
    }
    reverse(st.begin(), st.end());
    
    vector<long long> arr;
    string tmp = "";
    for(int i=0; i<st.size(); i++){
        if(st[i] == '0'){
            if(!tmp.empty()) { //이거 빼면 core dumped 
                arr.push_back(stol(tmp));
            }
            tmp = "";
            continue;
        }
        tmp += st[i];
    }
    if(!tmp.empty())
        arr.push_back(stol(tmp));
    
    // 소수 개수 세기
    for(int i=0; i<arr.size(); i++){
        if(isPrime(arr[i]))
            answer+=1;
    }
    return answer;
}

주의할 점

1. 진법 변환 후 reverse 필수.
2. stol(tmp)으로 문자열 tmp를 long으로 바꿔줄 때 tmp 문자열이 비어있으면 안된다.
   (stol 내부 로직을 확인해보니, 인자로 받은 string의 길이를 확인하지 않고 각 자리수의 char에 접근함)