[Programmers] k진수에서 소수 개수 구하기

코딩테스트 연습 - k진수에서 소수 개수 구하기

문제 유형

- 소수를 빠른 방법으로 구할 수 있는가 (몫과 나머지 연산)

- 문자열을 나누거나 합칠 수 있는가

 

TC1 시간초과 이유 

- for문을 다 돌면 O(n)

- 제곱근까지 돌면 O(n ** 0.5)

 

이 문제에서는 가까스로 제곱근으로 구하면 통과되지만, 

에라토스테네스의 체를 구현해야 할 수도 있다.

 

def n_to_kth(n, k):
    """
    정수 n 을 k 진수로 변환
    """
    tmp = ''
    while n > 0:
        n, rest = divmod(n, k)
        tmp = str(rest) + tmp   # 나머지를 거꾸로 출력

    return tmp


def is_prime_num(n):
    """
    소수 찾기 : N-1 ~ 2 까지의 수 중, 어떠한 수로도 나누어지지 않는 수
    """
    if n == 1:
        return False

    for i in range(2, int(n ** 0.5) + 1):
        if n % i == 0:
            return False

    return True


def solution(n, k):
    kth_number = n_to_kth(n, k)
    print(kth_number)
    numbers = kth_number.split('0')
    answer = 0
    for number in numbers:
        if number and is_prime_num(int(number)):  # 110011 split 시 공백 발생 ['11', '', '11']
            answer += 1

    return answer

 

 

알아두어야 할 알고리즘

- 에라토스테네스의 체

 

22. 에라토스테네스의 체

 

파이썬 내장함수 split 짚고가기

"0".split("0")
"00".split("0")
"100".split("0")
"010".split("0")
"001".split("0")

# result
['', '']
['', '', '']
['1', '', '']
['', '1', '']
['', '', '1']