k진수에서 소수 개수 구하기 C++ (프로그래머스 2022 KAKAO BLIND RECRUITMENT)

문제 설명

 

양의 정수 n이 주어집니다. 이 숫자를 k진수로 바꿨을 때, 변환된 수 안에 아래 조건에 맞는 소수(Prime number)가 몇 개인지 알아보려 합니다.

• 0P0처럼 소수 양쪽에 0이 있는 경우
• P0처럼 소수 오른쪽에만 0이 있고 왼쪽에는 아무것도 없는 경우
• 0P처럼 소수 왼쪽에만 0이 있고 오른쪽에는 아무것도 없는 경우
• P처럼 소수 양쪽에 아무것도 없는 경우
• 단, P는 각 자릿수에 0을 포함하지 않는 소수입니다.
  • 예를 들어, 101은 P가 될 수 없습니다.

예를 들어, 437674을 3진수로 바꾸면 211 0 2 0 1 0 1 0 11입니다. 여기서 찾을 수 있는 조건에 맞는 소수는 왼쪽부터 순서대로 211, 2, 11이 있으며, 총 3개입니다. (211, 2, 11을 k진법으로 보았을 때가 아닌, 10진법으로 보았을 때 소수여야 한다는 점에 주의합니다.) 211은 P0 형태에서 찾을 수 있으며, 2는 0P0에서, 11은 0P에서 찾을 수 있습니다.

정수 n과 k가 매개변수로 주어집니다. n을 k진수로 바꿨을 때, 변환된 수 안에서 찾을 수 있는 위 조건에 맞는 소수의 개수를 return 하도록 solution 함수를 완성해 주세요.

 

제한사항

• 1 ≤ n ≤ 1,000,000
• 3 ≤ k ≤ 10

입출력 예

 

n	k	result
437674	3	3
110011	10	2

소수는 1과 자기자신으로만 나누어지는 수를 말한다. 1은 포함되지 않는다.

 

 

풀이방법

 

문제를 천천히 따라가면 쉽게 풀 수 있다. 우선 입력으로 들어오는 n을 k진수의 형태로 바꾸어 준다. 그리고 0을 기준으로 이 숫자들을 쪼갠 뒤 이것이 소수인지 확인해 주면 간단하게 답을 구할수 있다.

주의할 점이 있는데, k진수로 바꾼 수가 매우 클 수 있으므로 정수 타입을 long 이상으로 설정해 주어야 한다.

 

 

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

using namespace std;

// 소수인지 확인하는 함수
bool IsPrime(long long int n) {
    if(n < 2)
        return false;
    
    for(int i=2; i<=sqrt(n); i++) {
        if(n%i == 0)
            return false;
    }
    return true;
}

int solution(int n, int k) {
    string number = "";
    int answer = 0;
    vector<long long int> prime_numbers;
    // n을 k 진수로 바꾸어 문자열로 저장한다.
    while(n > 0) {
        number = to_string(n%k) + number;
        n /= k;
    }
    string tmp = "";
    // k 진수로 바뀐 숫자를 하나하나 읽으며 0이 나올 때 마다 앞에 모인 숫자들이 소수인지 확인 한다.
    for(int i=0; i<number.size(); i++) {
        if(!tmp.empty() && number[i] == '0' && IsPrime(stoul(tmp))) {
            cout << "tmp" << tmp << endl;
            answer++;
            tmp = "";
        }
        else if(number[i] == '0') {
            tmp = "";
        }
        else
            tmp += number[i];
        cout << tmp << endl;
    }
    
    // 마지막 tmp 확인
    if(!tmp.empty() && IsPrime(stoul(tmp)))
        answer++;

    return answer;
}