✍️Today I Learned

📅 2025-07-25

• 코드카타 - k진수에서 소수 개수 구하기
• 커리어데이

코드카타 - k 진수에서 소수 개수 구하기

문제

프로그래머스 k진수에서 소수 개수 구하기
양의 정수 n이 주어진다. 이 숫자를 k진수로 바꿨을 때 변환된 수 안에 조건에 맞는 소수의 개수를 반환해라

조건

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

제한사항

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

풀이

Pseudo code

1. n을 k진수로 변환 후 문자열로 변환
2. 0으로 문자열 나누기
3. 나눠진 문자열이 소수인지 확인하여 answer++

제출 코드

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

using namespace std;
bool IsPrime(long long n)
{
    if(n<=1) return false;
    for(long long i = 2; i*i<=n; i++)
    {
        if(n%i==0) return false;
    }
    
    return true;
}

int solution(int n, int k) {
    int answer = 0;
    string base_k;
    if(k==10) base_k = to_string(n);
    else{
        while(n>0)
        {
            base_k+=to_string(n%k);
            n = n/k;
        }
        reverse(base_k.begin(), base_k.end());
    }
    string::size_type idx=0;
    while(1)
    {   
        if(base_k[idx]=='0') 
        {
            idx++;
            if(idx>=base_k.size()) break;
            continue;
        }
        
        string temp="";
        if(base_k.find('0', idx)!=string::npos)
        {   
            temp = base_k.substr(idx, base_k.find('0', idx)-idx);  
            if(IsPrime(stoll(temp))) answer++;
            idx = base_k.find('0', idx);            
        }
        else
        {
            temp = base_k.substr(idx);
            if(IsPrime(stoll(temp))) answer++;
            break;
        }
    }
    return answer;
}

---

💡 느낀 점 (What I Felt)

소수를 먼저 구하고 조건에 맞는 문자열이 문자열안에 있는 지 확인하는 코드를 짜다가 소수를 구하는 범위가 말도 안될거 같아 문제를 다시 분석하고 푸는 방식을 바꾸었다.

문제를 분석하는 것을 좀 더 연습해야겠다.