문제 링크

---

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

문제 풀이

---

양의 정수 n과, k가 주어질 때 n을 k진수로 변경하여 소수를 찾으면 되는 간단한 문제이다.

이 문제에 약간의 함정이 있는데 정수 n을 k진수로 변경하고 조건에 맞게 소수를 찾기위해 문자열로 변경을 해준 후 다시 숫자로 변경을 해주면서 문제를 풀게된다. 문제는 문자열에서 숫자로 변경 할 때 발생하는데 양의 정수 n의 범위는 1~1,000,000으로 int타입으로 저장을 해도 문제가 없다. 이를 k진수로 변경하게 될 경우 자릿수가 커지는 경우가 생기고 문자열로 변경할때는 문제가 되지 않지만 이를 다시 int 타입 변수에 저장하게 될 경우 범위를 벗어나 런타임 에러가 발생한다. 그렇기 때문에 int 타입이 아닌 long 타입으로 저장을 해주어야 한다. 추가로 제곱근을 이용하여 소수를 찾도록 프로그래밍 하였으며 다음과 같이 풀었다.

• 양의 정수 n -> k진수 -> 문자열로 변경
• 문자열의 크기 만큼 탐색하면서 벡터에 저장
• 0을 만나면 벡터에 저장된 값이 소수인지 확인
  • 소수면 카운트 해주고 벡터 초기화
  • 소수가 아니라면 카운트 하지않고 벡터 초기화
• 탐색이 끝난 후 벡터의 크기가 0이 아니라면 소수 검사

정답 코드

---

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

using namespace std;

//소수인지 검사 해주는 함수
bool isPrime(vector<char> v) {

    
    string str;
    for (int i = 0; i < v.size(); i++) {
        str.push_back(v[i]);
    }
    long num = stol(str); // 이 부분을 간과함 n을 k진수로 바꿨을때 자릿수가 int 타입으로 표현할 수 있는 범위를 훨씬 넘어설 수 있다.
    if (num < 2) return false;
    for (int i = 2; i <= sqrt(num); i++) {
        if (num % i == 0) {
            return false;
        }
    }
    return true;
}

//k진수로 바꿔 문자열로 변경해주는 함수 
string changeNum(int a, int b) {
    string str = "";
    stack<char> temp;
    //10진
    while (a >= b) {
        
        temp.push((a % b)+'0');
        a = a / b;
    }
    temp.push(a+'0');

    while (!temp.empty()) {
        str.push_back(temp.top());
        temp.pop();
    }
    return str;
}

int solution(int n, int k) {
    int answer = 0;
    vector<char> v;
    string str = changeNum(n, k); //k진수로 변경

    // 0을 만나면 그 전까지 저장된 값이 소수인지 확인
    for (int i = 0; i < str.size(); i++) {
        if (str[i] == '0') {
            if (!v.empty()) {
                if (isPrime(v)) {
                    answer++;
                }
                v.clear();
            }
            else {
                continue;
            }
        }
        else {
            v.push_back(str[i]);
        }
    }

    // 마지막에 0을 만나지못해 벡터에 값이 남아있는 경우 처리
    if (!v.empty()) {
        if (isPrime(v)) {
            answer++;
        }
        v.clear();
    }
    return answer;
}