Programmers - k진수에서 소수 개수 구하기

---

title: Programmers - k진수에서 소수 개수 구하기
date: 2022-07-18
tags:

• Algorithm

---

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

문제 요약

숫자 n을 k진수 방식으로 표기한다.
이를 0을 구분자로 파싱하여 나온 숫자들 중 소수의 개수를 count하여 return한다.

문제 풀이

개인적으로 어려운 문제였다.
늘 성능과 좋은 프로그램을 작성할 수 있도록 구현을 하는데, 이 문제는 그러한 원칙을 약간 비꼬아 접근해야 풀 수 있었다.

파싱하여 나올 수 있는 가장 큰 값은 3진수 표현에서 1이 12번 연속하여 나오는 경우이다. 이 값은 36비트가 필요하다.
int형 범위를 벗어나므로, long long을 사용하여야 한다.
하지만 0이 적절하게 배치될수록 판별할 최대값은 작아지므로, 파싱 후 소수 구분을 하는 과정이 적절하다.
k진수 방식으로 변환하여 string으로 저장 후, 0이 나올 때마다 이전 값을 파싱하여 2 혹은 3 이상의 홀수의 경우에만 vector에 넣는다.

처음 생각한 방식은 에라토스테네스의 체 방식을 이용하여 root (최대값) 만큼 소수를 구한 후, 소수들을 이용하여 수를 판별한다.
생각보다 판별해야할 소수가 많았으며, 이로 인하여 시간 초과가 발생하였다.
이에 관한 테스트 케이스를 찾아보다가, 결국 이렇게 소수를 구하는 방식은 해당 문제에 적합하지 않다는 것을 알았다.
결국 2부터 root (최대값) 까지의 모든 수를 이용하였으며, 소수를 따로 구하는 시간보다 이렇게 모든 수를 이용하는 것이 훨씬 빨랐다.

한 가지 이해가 안 되는 점이 있다.

for ( long long i = 2 ; i <= sqrt ( llMaxPrime ) ; ++i )

위와 같이 작성하였으며, llMaxPrime은 파싱한 값의 최대값이 아닌, 그 최대값의 비트 개수만큼 사용하였을 때 표현 가능한 최대의 수이다.
충분한 범위를 주었으나, 14번 테스트 케이스가 계속하여 실패하였다.
해당 문제를 겪은 다른 유저가 sqrt ( llMaxPrime ) + 1 처럼 끝에 1을 더해주어 문제를 해결하였다는 것을 확인하였다.
하지만 +1으로는 해결이 되지 않았으며, 아래와 같이 i값을 2나 빼주어야 테스트 케이스가 무사히 통과되었다.

for ( long long i = 2 ; i - 2 <= sqrt ( llMaxPrime ) ; ++i )

특정 방식이 늘 최선의 성능을 가져오지 않는다는 것을 알 수 있었다.

### 프로그램 ```c++ #include #include #include #include

using std :: vector ;
using std :: string ;

int solution ( int n , int k )
{
int answer = 0 ;
vector < long long > vStringParseNumber ;
string strKDigit = "" ;
int iMaxDigit = 0 ;
const char * cpString ;
int iStringSize ;
int iTemp = 0 ;
long long llMaxPrime = 0 ;
long long llSubstrNumber = 0 ;

while ( 0 != n )
{
    strKDigit += '0' + n % k ;
    n /= k ;
}
std :: reverse ( strKDigit.begin () , strKDigit.end () ) ;
cpString = strKDigit.data () ;
iStringSize = strKDigit.size () ;

for ( int i = 0 ; i < iStringSize ; ++i )
{
    if ( ( 0 != iTemp ) && ( '0' == cpString [ i ] ) )        // Parse number
    {
        llSubstrNumber = std :: stoll ( strKDigit.substr ( i - iTemp , iTemp ) ) ;

        if ( 2 == llSubstrNumber || ( ( 0 != ( llSubstrNumber % 2 ) ) && ( 1 != llSubstrNumber ) ) )            // Odd number
        {
            vStringParseNumber.emplace_back ( llSubstrNumber ) ;
            iMaxDigit = std :: max ( iMaxDigit , iTemp ) ;
        }

        iTemp = 0 ;
    }
    else if ( '0' != cpString [ i ] )
    {
        ++ iTemp ;
    }
}
if ( 0 != iTemp )
{
    llSubstrNumber = std :: stoll ( strKDigit.substr ( iStringSize - iTemp , iTemp ) ) ;

    if ( 2 == llSubstrNumber || ( ( 0 != ( llSubstrNumber % 2 ) ) && ( 1 != llSubstrNumber ) ) )                // Odd number
    {
        vStringParseNumber.emplace_back ( llSubstrNumber ) ;
        iMaxDigit = std :: max ( iMaxDigit , iTemp ) ;
    }
}

iTemp = vStringParseNumber.size () ;

for ( int i = 0 ; i < iMaxDigit ; ++i )                    // Find max prime number to check
{
    llMaxPrime = llMaxPrime * 10 + iMaxDigit - 1 ;
}
for ( long long i = 2 ; i + 1 <= sqrt ( llMaxPrime ) + 1 ; ++i )
{
    for ( int j = 0 ; j < iTemp ; ++j )
    {
        if ( ( vStringParseNumber [ j ] != i ) && ( 0 == ( vStringParseNumber [ j ] % i ) ) )
        {
            vStringParseNumber.erase ( vStringParseNumber.begin () + j ) ;
            -- iTemp ;
            -- j ;
        }
    }
}


return vStringParseNumber.size () + answer ;

}
```