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

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

프로그래머스

나의 풀이 - 시간초과

def is_prime_number(x):
    # 2부터 (x - 1)까지의 모든 수를 확인하며
    if x < 2:
        return False
    for i in range(2, x):
        # x가 해당 수로 나누어떨어진다면
        if x % i == 0:
            return False # 소수가 아님
    return True # 소수임

def solution(n, k):
    answer = 0
    decimal = []
    while n >= k:
        decimal.append(n%k)
        n = n//k
    decimal.append(n)
    decimal.reverse()
    
    for sd in [i for i in ''.join(str(e) for e in decimal).split('0')]:  
        if sd.isdigit() and is_prime_number(int(sd)):
            answer += 1
    return answer

나의풀이 - 시간초과 해결

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

def solution(n, k):
    answer = 0
    decimal = []
    while n >= k:
        decimal.append(n%k)
        n = n//k
    decimal.append(n)
    decimal.reverse()
    
    for sd in [i for i in ''.join(str(e) for e in decimal).split('0')]:  
        if sd.isdigit() and is_prime_number(int(sd)):
            answer += 1
    return answer

• 소수인지 확인하는 함수가 문제였다.
• 소수인지 확인하기 위해 끝까지 찾을필요 없이 루트를 씌운 만큼만 나누어 떨어지는지 확인하면 됐다.

나의풀이 - 개선

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

def solution(n, k):
    answer = 0
    decimal = ""
    while n > 0:
        decimal += str(n%k)
        n = n//k
    for sd in decimal[::-1].split('0'):  
        if sd == "":
            continue
        if is_prime_number(int(sd)):
            answer += 1
    return answer

• 이진수로 변경하는 로직도 굳이 배열을 사용하지 않고 문자열로 사용하면 더 깔끔했다.
• 문자열을 거꾸로 뒤집기 위해 [::-1]를 사용하면 유용하다.