코딩테스트 : k진수에서 소수 개수 구하기

해당 문제는 특정 진수로 n을 변환시키는 방법과 문자열에서 특정 문자를 기준으로 나누는 방법, 소수를 구하는 방법을 사용해야되는 문제이다. 

첫 번째 시도

#include <string>
#include <vector>
#include <stack>
#include <sstream>
#include <algorithm>

using namespace std;

int solution(int n, int k) {
    int answer = 0;
    
    stack<int> s;
    
    //n을 k로 나누었을때 나오는 나머지가 해당 정수를 k로 나타낼 때 나오는 값이다.
    while(n != 0)
    {
        s.push(n % k);
        n /= k;
    }
    
    string str = "";
    
    while(!s.empty())
    {
			  //stack에는 반대로 저장되었을 테니 한개씩 꺼내서 뒤집어준다.
        str += to_string(s.top());
        s.pop();
    }
    //이제보니 stack에 저장하는 방법보다 string에 반대 순서로 일단 저장하고 reverse 함수로
    //뒤집는 방법이 더 좋아보인다.
    
    stringstream ss(str);
    string num;
    vector<int> numV;
    
    //문자가 0을 기준으로 num에 저장한다.
    while(getline(ss, num, '0'))
    {
		    //0이 연속으로 등장 시 ""이 num에 저장되니 ""이면 넘어간다.
        if (!num.empty())
		        //공백이 아니면 해당 숫자를 저장한다.
            numV.push_back(stoi(num));
    }
    
    //저장된 수들 중 가장 큰 값을 뽑아
    int Max = *max_element(numV.begin(), numV.end());
    
    //가장 큰 값의 크기만한 vector를 만들어준다.
    vector<bool> primeN(Max + 1, false);
    //0과 1은 항상 소수가 아니니 true로 만든다.
    primeN[0] = primeN[1] = true;
    
    //아레스토테네스의 체로 소수로 판별되면 true, 아니면 false를 남겨준다.
    for (int i = 2; i * i <= Max; i++) 
    {
        if (!primeN[i]) 
        {
		        //i값이 증가하는 과정에서 현재 i값이 false라면 i는 소수이므로 i는 판별하지않는다.
		        //ex) i = 2부터 3,4로 진행되는데 4는 i가 2일때 true로 바뀌었다. 하지만 7은 앞에
		        //수들에 의해 바뀌지 않았으므로 앞에 수들로 나눌 수 없다는 뜻이 되며 이는 소수임을 뜻한다.
            for (int j = i * i; j <= Max; j += i) 
            {
                primeN[j] = true;
            }
        }
    }
    
    //저장된 숫자들이 소수이면 answer를 1 증가시킨다.
    for(int i : numV)
    {
        if(primeN[i] == false && i > 1)
            answer++;
    }
    
    return answer;
}

해당 방식의 문제는 primeN의 크기가 매우 커질 수 있다는 것이다. 만약 Max의 크기가 10^9이라면 125MB 이상 필요로하며 메모리 초과 오류가 발생한다. 때문에 Vector로 모든 수를 저장하지 않고 문제를 해결해야한다.

두 번째 시도

#include <string>
#include <vector>
#include <stack>
#include <sstream>
#include <algorithm>

using namespace std;

bool isPrime(long long num) {
    if (num < 2) return false;
    //위 방법에서 저장하면서 한번 소수인지 판별한 방법을 매번 사용해 확인해준다.
    for (long long i = 2; i * i <= num; i++) {
        if (num % i == 0) return false;
    }
    return true;
}

int solution(int n, int k) {
    int answer = 0;
    
    stack<int> s;
    
    while(n != 0)
    {
        s.push(n % k);
        n /= k;
    }
    
    string str = "";
    
    while(!s.empty())
    {
        str += to_string(s.top());
        s.pop();
    }
    
    stringstream ss(str);
    string num;
    
    while(getline(ss, num, '0'))
    {
        if (!num.empty())
        {
		        //vector에 저장하는 과정을 빼고 바로 소수인지 체크한다.
            if(isPrime(stoll(num)))
                answer++;
        }
    }

    return answer;
}

해당 코드에서는 매번 num값이 소수인지 검사하며 소수인 경우 answer을 증가시키는 방식으로 구현되었다. 이 방식을 사용하면 메모리를 많이 차지하지 않으며 효율적인 모습이다.

 

★소수를 전부 저장하는 방식(에라스토테네스의 체)은 특정 값보다 작은 모든 소수를 구하는 방법 등에 사용하고 특정 값이 소수인지 확인할 때는 매번 확인하는게 좋아보인다.