프로그래머스 - k진수에서 소수 갯수 구하기 (2022 KAKAO BLIND RECRUITMENT) / Level 2 / Python

문제 📋

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

풀이 📝

import math

def is_prime_num(num):  # 소수인지 판별
    if num == 1:
        return False
    
    for i in range(2, int(math.sqrt(num) + 1)):  # num의 제곱근까지만 보면 그 이후론 대칭임
        if num % i == 0:
            return False
    return True

def solution(n, k):
    answer = 0
    k_num = 0
    multiple = 1
    
    while n >= k:  # k진수 만들어주기
        k_num += (n % k) * multiple
        n = n // k
        multiple *= 10
    k_num += n * multiple
    
    cand = str(k_num).split('0')  # 0 기준으로 분리
    
    for i in cand:
        if i.isdigit() and is_prime_num(int(i)):  # 숫자이면서 소수이면 조건을 만족
            answer += 1
            
    return answer

소수인지 판별하는 것은 순차탐색하면서 나누어지는 수가 있는지 확인하면 되고
k진수로 만들어주는 것도 k로 나눠주면서 나머지들을 적절히 조합해서 만들수 있었다.
문제의 조건 만족 여부를 찾는 것도 k진수를 0기준으로 split() 해주면 쉽게 찾을 수 있다.

그러나 이렇게 풀었더니 이 문제의 효율성 테스트를 통과하지 못했다.
그래서 어디서 시간복잡도를 줄일 수 있을지 고민끝에 is_prime_num() 함수에서 O(n)으로 소수인지 판별하는 것이 비효율적이라고 생각했고
분명 수학적으로 탐색 범위를 줄일 방법이 있을거라 생각했다.

곰곰히 생각해보면 어떤 수 x가 소수인지 판별하는 것은 그 수의 약수들을 찾는 것이고 약수가 1과 자기자신 뿐이면 소수이다.

그런데 약수는 루트 x 기준으로 대칭이다.
따라서 1~x까지 다 나누어 볼 필요없이 루트 x까지만 나눠보면 그 수가 소수인지 알 수 있다.