[n진수] k진수에서 소수 개수 구하기 - 2022 KAKAO BLIND RECRUITMENT

해결 방법

문제에서 원하는 소수에 대한 조건은 다음과 같다.

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

겉보기에는 복잡한 조건을 가지고 있는 것처럼 보이지만, 0을 기준으로 split해서 나온 숫자들 중에서 소수는 몇 개인지만 계산하면 된다.

 

테스트케이스 1, 11번에서 틀리는 경우에는 소수를 추출해서 판별할 때 long 자료형을 사용해보자. 진수 변환을 하면 숫자가 매우 길어지기 때문에 int보다는 long을 선택하는 것이 좋다.

그리고 테스트케이스 12번에서 틀리는 경우에는 소수 판별 함수에서 정수 0까지 판별할 수 있도록 반영해보자.

 

 

소스 코드

#include <algorithm>
#include <math.h>
using namespace std;

// 진수 변환 함수
string converter(int k, int n){
    if(n==0) return "0";
    string str="";
    int r;
    while(n>0){
        r=n%k; //나머지
        n/=k; //몫
        str+=r+'0';
    }
    reverse(str.begin(), str.end());
    return str;
}

// 소수 판별 함수
bool prime_check(long n) {
    if(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;
    int zero_pos = -1;
    string str = converter(k, n);
    long num;
    for(int i=0;i<str.length();i++){
        if(str[i]=='0') {
            if(i-zero_pos-1==0) continue; // 0이 연속으로 나와서 추출할 숫자가 없는 경우
            num = stol(str.substr(zero_pos+1, i-zero_pos-1)); // P0 또는 0P0 형태로 추출
            if(prime_check(num)) answer++;
            zero_pos=i;
        }
        else if(i==str.length()-1) { // 0P 또는 P 형태로 추출
            num = stol(str.substr(zero_pos+1));
            if(prime_check(num)) answer++;
        }
    }
    return answer;
}

 

테스트케이스 16개 모두 성공

 

문제 출처 : https://school.programmers.co.kr/learn/courses/30/lessons/92335