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

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

새로 알게된 것들

1. 숫자의 루트값을 구하기 위해 import math를 하지 않더라도 파이썬에선 손쉽게 구할 수 있다.

number ** 0.5 # 모듈을 끌어다 쓰지 않아도 되서 간편하다
math.sqrt(number)
math.pow(number, 0.5)
# 모두 같은 표현

2. 가장 손쉽고 꽤 빠른 소수 구하는 메서드

def is_prime(number):
    i = 2
    while i * i <= number: # number의 루트를 구하지 않고 이렇게 표현하는 것이 더 깔끔한것 같다.
        if number % i == 0:
            return False
        i += 1
    return False if number <= 1 else True

풀이

1. 소수를 구하는 메서드를 구현한다. 이 때 소수를 구할 숫자의 절반을 범위로 정해서 구현하면 테스트1에서 시간초과가 나온다. 질문하기를 보고 제곱근으로 해야 더 시간단축을 할 수 있다는 것을 보고 구현했다.
2. 최근에 정규표현식 문제를 좀 풀어서 정규표현식으로 구현했는데 이것때문에 테스트12에서 계속 런타임에러가 났다. 잘 모르겠으면 확실하게 문자열.split()메서드를 이용해서 구현하자.

코드

def is_prime(number):
    i = 2
    while i * i <= number:
        if number % i == 0:
            return False
        i += 1
    return False if number == 1 else True
    
def solution(n, k):
    answer = 0
    str_n = ''
    while n > 0:
        str_n = str(n % k) + str_n
        n //= k
    
    for num in str_n.split('0'):
        if num == '':
            continue
        if is_prime(int(num)):
            answer += 1
    
    return answer

다른 사람 풀이를 보며 알게 된 점

질문하기를 최대한 보지 않을려고 노력했지만 시간초과가 난 것을 보고 이렇게 주먹구구식으로 소수를 구하면 안되고 에라토스테네스의 체같은 알고리즘을 이용하는 것인 줄 알고 봤다가 그냥 내가 틀렸다는 것을 깨달았다. 소수 구할 때 제곱근으로 시간단축하는 것, 미숙한 정규표현식 사용으로 인한 런타임 에러 등 확실하다고 생각했는데도 여러 부분에서 틀려서 좀 슬프다.