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

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

프로그래머스

 

전체 코드

#include <string>
#include <vector>
#include <stack>
#include <algorithm>
#include <iostream>
using namespace std;
bool isPrime(long long int n) // 제곱근 판별 함수
{
    if(n==1)
        return false;
    
    for(long long int i=2;i*i<=n;i++) // 제곱근 방법
    {
        if(n%i==0)
            return false;
    }
    
    return true;
}

string convert(long long int n, int k) // 진수 변환 함수
{
    stack<long long int> s;
    string str;
    while(n!=0)
    {
        str+=to_string(n%k);
        n/=k;
    }
    
    reverse(str.begin(), str.end());
    return str;
}


// 4095,2 int 오버플로우
int solution(int n, int k) {
    int answer = 0;
    string s = convert(n, k);
    string temp;
    for(int i=0;i<s.length();i++)
    {
        if(s[i]!='0')
            temp+=s[i];
        else // 현재 위치 i에 0 발견
        {
            if(temp.length()!=0 && isPrime(stol(temp))) 
            {
                if(i-temp.length()-1>=0 && s[i-temp.length()-1]=='0') // 0P0
                    answer++;
                else if(i-temp.length()==0) // P0
                    answer++;
            }
            temp="";
        }
    }

    
    if(temp.length()!=0 && isPrime(stol(temp)))
    {
        if(s.length()-temp.length()>=0&&s[s.length()-temp.length()-1]=='0') // 0P
            answer++;
        else if(s.length()-temp.length()==0) // P
            answer++;
    }
            
    
    return answer;
}

 

풀이 방법

n을 k진수로 바꾼 결과를 s라고 하자.

P는 자릿수에 0을 포함하지 않는 소수이기에 s를 왼쪽에서 0을 만날 때까지 읽어 소수 P를 만들 수 있다.

0을 만날 때까지 숫자를 읽어 붙인 스트링을 temp라고 하자.

읽다가 0을 만난다면 temp가 소수 P의 후보가 되는 것이다.

이제 temp만을 가지고 문제에서 요구하는 조건에 맞는 소수인지 판별하여 카운트하면 끝이다.

 

 

소수 판별 함수

bool isPrime(long long int n) // 제곱근 판별 함수
{
    if(n==1)
        return false;
    
    for(long long int i=2;i*i<=n;i++) // 제곱근 방법
    {
        if(n%i==0)
            return false;
    }
    
    return true;
}

isPrime함수에 정수 n을 넘겨 소수인지 아닌지 true, false를 반환하는 함수이다.

소수 판별을 2부터 n까지 다 나눈 나머지를 검사한다면 테스트케이스 1번에서 시간초과가 난다.

 

진수 변환 함수

string convert(long long int n, int k) // 진수 변환 함수
{
    string str;
    while(n!=0)
    {
        str+=to_string(n%k);
        n/=k;
    }
    
    reverse(str.begin(), str.end());
    return str;
}

k진수로 바꾼 문자열을 반환하게 함수를 만들었다.

 

solution 함수

int solution(int n, int k) {
    int answer = 0;
    string s = convert(n, k);
    string temp;
    for(int i=0;i<s.length();i++)
    {
        if(s[i]!='0')
            temp+=s[i];
        else // 현재 위치 i에 0 발견
        {
            if(temp.length()!=0 && isPrime(stol(temp))) 
            {
                if(i-temp.length()-1>=0 && s[i-temp.length()-1]=='0') // 0P0
                    answer++;
                else if(i-temp.length()==0) // P0
                    answer++;
            }
            temp="";
        }
    }

    
    if(temp.length()!=0 && isPrime(stol(temp)))
    {
        if(s.length()-temp.length()>=0&&s[s.length()-temp.length()-1]=='0') // 0P
            answer++;
        else if(s.length()-temp.length()==0) // P
            answer++;
    }
            
    
    return answer;
}

 

 

s에는 convert함수를 통해 k진수로 변환된 문자열이 저장될 것이다.

string s = convert(n, k);

 

s를 왼쪽에서 읽어 들여 temp에 숫자를 붙여가며 소수 P를 만들 것이다.

string temp;
    for(int i=0;i<s.length();i++)
    {
        if(s[i]!='0')
            temp+=s[i];
        else // 현재 위치 i에 0 발견
        {
            if(temp.length()!=0 && isPrime(stol(temp))) 
            {
                if(i-temp.length()-1>=0 && s[i-temp.length()-1]=='0') // 0P0
                    answer++;
                else if(i-temp.length()==0) // P0
                    answer++;
            }
            temp="";
        }
    }

0이 아니라면 tmep에 붙여준다.

 

0이라면 이제 소수인지 판별을 하고 소수가 맞다면 조건에 맞는 소수인지 확인해야 한다.

if(temp.length()!=0 && isPrime(stol(temp)))

temp의 길이가 0이 아니여야지 소수로 바꾸고 조건검사가 가능하다.

temp가 소수가 가능하다면 if문이 참이 될 것이다.

 

                if(i-temp.length()-1>=0 && s[i-temp.length()-1]=='0') // 0P0
                    answer++;
                else if(i-temp.length()==0) // P0
                    answer++;
            }
            temp="";

먼저, 이제껏 읽어 들인 문자열 temp의 길이를 통해 P의 시작 인덱스와 끝 인덱스를 계산할 수 있다.

i-temp.length()-1은 0P0에서 첫 번째 0의 위치를 나타낸다. '0'P0에서 '0'을 말하는 것이다.

이것이 앞에 0이 있으려면 이 인덱스(i-temp.length()-1)의 위치가 0보다 커야지 앞에 문자가 존재할 수 있고

s[i-temp.length()-1]의 위치에 0이 있다면 P앞에 0이 존재하는 것이다.

 

0P0에서 두 번째 0의 위치 0P'0'인지 검사를 왜 안 하냐면 이미 현재 위치 i에서 0이 만났기에

else문에 들어온 거 기 때문에 두 번째 위치 0은 존재한다.

 

P0의 경우 소수 P의 시작 인덱스 i-temp.length()가 0이라면 소수 P가 젤 처음으로 시작한다는 것을 알 수 있다. 마찬가지로 현재 위치 i에 0은 존재하니 따로 조건을 추가하지 않는다.

 

조건 검사 후에 temp를 아무것도 없는 문자열 ""로 초기화 시켜준다.

 

아래의 if문은 0P, P 조건을 검사하기 위한 if문이다.

0P, P의 경우 위의 for문을 돌고 반복문이 끝났지만 temp에 문자열이 남아있을 때이다.

s의 끝에 0이 없어 0을 만나지 못해 temp를 검사하지 못하고 반복문이 끝났기 때문이다.

    if(temp.length()!=0 && isPrime(stol(temp)))
    {
        if(s.length()-temp.length()>=0&&s[s.length()-temp.length()-1]=='0') // 0P
            answer++;
        else if(s.length()-temp.length()==0) // P
            answer++;
    }

 

 

 

if(s.length()-temp.length()>=0&&s[s.length()-temp.length()-1]=='0') // 0P

0P의 형태로 있는지 검사하면 된다.

s[s.length()-temp.length()-1]의 위치에 0이 있으면 0P의 형태이다.

 

else if(s.length()-temp.length()==0)

P의 형태는 P의 시작의 인덱스가 0이면 P의 형태이다.