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

➡️ 문제

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

아이디어 정리

함수 생성

• 10 진수를 k진수로 변경하는 trans() 함수.
• 소수인지 판별하는 is_prime() 함수.

1. n 을 k 진수로 변경한다.
2. 변경한 수를 0 으로 split 한다.
3. 리스트에서 빈 문자열을 제거한다.
4. 리스트를 돌면서 소수여부를 검사한다.
5. 해당 수가 소수이면 count 를 올려준다.

✅ 코드

첫 시도

def is_prime(n):
    if n == 1:
        return False
    
    for i in range(2, n // 2):
        if n % i == 0:
            return False
    return True

def trans(n, q):
    num = ''
    while n > 0:
        n, mod = divmod(n, q)
        num += str(mod)
    return num[::-1]
    
def solution(n, q):
    count = 0
    num_lst = trans(n, q).split('0')
    num_lst = ' '.join(num_lst).split()

    for n in num_lst:
        if is_prime(int(n)):
            count += 1
    return count

히든 케이스 1개에서 시간초과가 발생하였다.

➡️ 시간 초과가 나는 경우를 생각해 보자.
해당 풀이에서 시간을 줄일 수 있는 코드는 is_prime 함수에서 약수를 구하는 공식이다.
2부터 n // 2 까지 순회하며 검토하는 것은 짝지어 질 수 있는 약수까지 모두 검토하는 것이기 때문에 비효율적이다.
예를 들어 n = 21 일 때 3과 7은 짝지어져 3으로 나눴을 때 만으로 판별이 가능한데 7까지 순회하여 추가로 검토하게 된다.
따라서 소수를 판별할 때 2 부터 n의 제곱근 까지만 순회하여 검토해도 판별이 가능하다.

수정 코드

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

def trans(n, q):
    num = ''
    while n > 0:
        n, mod = divmod(n, q)
        num += str(mod)
    return num[::-1]

def solution(n, q):
    count = 0
    num_lst = trans(n, q).split('0')

    for n in num_lst:
        if n != '' and is_prime(int(n)):
            count += 1
    return count

무난하게 통과되었다!