[C++] 프로그래머스: k진수에서 소수 개수 구하기

🔗 문제

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

프로그래머스

#2022 KAKAO BLIND RECRUITMENT

 

📝 풀이

 

 

자꾸 틀리는 바람에 인터넷에 검색해서 풀었다. 

 

 

제한사항

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

 

1. 먼저 진수를 바꿔보자. 

🔗참고: https://viin.tistory.com/97

[C++] 진수 변경: 숫자N을 A진법으로 바꿔보기

 

std::string num="";
while(n)
{
    num += std::to_string(n%k);
    n/=k;
}
std::reverse(num.begin(), num.end());

 

2. 반복문으로 소수를 찾아낸다. 

 

이때 각 문자열을 0과 0이 아닌 숫자로 나눈다. 자세한 사항은 아래 코드의 주석을 보자. 

for(int i=0; i<num.size(); ++i)
{
    // tmp에 저장해서 소수인지 확인
    if(num[i]!='0')
        tmp+=num[i];
	
    // 0을 만나면 지금껏 저장한 tmp를 판단한다.  ex) 110
    // 0이 아닌 숫자가 마지막에 와도 판단 대상 ex) 11
    
    if((num[i]=='0' || i==num.length()-1)
       && tmp.size()!=0)
    {
        if(isPrime(std::stoll(tmp), k))
            answer++;

        tmp="";
    }
}

 

 

2-1. 소수 판별

🔗참고: https://viin.tistory.com/96

bool isPrime(long long n, int k)
{
    if(n==1)
        return false;
    
    for(long long i=2; i<=std::sqrt(n); ++i)
    {
        if(n%i == 0)
            return false;
    }
    
    return true;
}

 

 

💾 소스

 

틀린 코드는 아래와 같은데 짧으니 한번 읽으면서 이상한 점을 찾아보세요.

참고로 이 소스는 1번과 11번 테이스 케이스를 통과하지 못한다.

 

#include <string>
#include <vector>
#include <cmath>
#include <algorithm>
using namespace std;

bool isPrime(long long n, int k)
{
    if(n==1) return false;
    
    for(long long i=2; i<=std::sqrt(n); ++i)
    {
        if(n%i == 0)
        	return false;
    }
    
    return true;
}

int solution(int n, int k)
{
    int answer = 0;
    
    //1. n을 k진수로 변경
    std::string num="";
    while(n)
    {
        num += std::to_string(n%k);
        n/=k;
    }
    std::reverse(num.begin(), num.end());
    
    //2. P 조건 확인
    std::string tmp;
    for(int i=0; i<num.size(); ++i)
    {
    	// 0이 아니면 소수 확인 대상
        if(num[i]!='0')
            tmp+=num[i];
        
        if((num[i]=='0' || i==num.length()-1)
           && tmp.size()!=0)
        {
        	// 3. 소수 판별
            if(isPrime(std::stoi(tmp), k))
                answer++;
            
            tmp="";
        }
    }

    return answer;
}

 

10진수를 2진수로 바꾸게 되면 문자열이 길어지게 되면서 int 에 담지 못하는 일이 일어난다. 

다른건 long long 으로 커버를 했는데 std::stoi 를 사용했기 때문에 틀렸다. 

 

std::stoll로 string to long long 변환 해주어야 한다.