프로그래머스 Lv2 문제입니다. 실전에 대비하기 위해 60분 시간제한을 두고 풀었습니다.

문제

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

[나의 풀이]

⌛ 시간초과 (1개 케이스 시간초과)

def k_jinsoo(k,n):
    
    now = 1
    m = 13
    jinsoo = ''
    rest = n
    
    for i in range(m-1,-1,-1):
        share, rest = divmod(rest,k**i)
        jinsoo += str(share)

    return jinsoo
    
def solution(n, k):
    answer = 0
    global jinsoo
    
    jinsoo = ''
    
    jinsoo = k_jinsoo(k,n)
        
    jinsoo = jinsoo.split("0")
    
    Primes = set()
    
    for x in jinsoo:
        if x == "" or x == "1":
            continue
        else:
            x = int(x)
            
            if x in Primes:
                answer += 1
                continue
            else:
                isPrime = True
                for i in range(2,x):
                    if x%i==0:
                        isPrime = False
                        break
                        
                if isPrime:
                    Primes.add(x)
                    answer += 1

    return answer

입력된 수 n 을 k진수로 변환한 뒤, 0을 간격으로 소수의 갯수를 구하는 문제입니다.🐪🐪🐪

K진수로의 변환은 divmod()를 활용하여 몫과 나머지를 연산하는 방식으로 구현하였습니다. 이때, k의 최솟값은 3, n의 최댓값은 1000000이기 때문에 변환될 수 있는 k진수는 최대12자릿수이므로 이를 기준으로 나누며 변환하였습니다.

split("0")을 활용하여 판별해야하는 소수 대상을 분리하는 방식으로 구현하였
지만 1개 케이스에서 시간초과가 발생하여 시간이 지체되었습니다.

[다른 사람의 풀이1]

def solution(n, k):
    word=""
    while n:            # 숫자를 k진법으로 변환
        word = str(n%k)+word
        n=n//k
        
    word=word.split("0")  # 변환된 숫자를 0을 기준으로 나눈다.
    
    count=0
    for w in word:
        if len(w)==0:    # 만약 0또는 1이거나 빈공간이라면 continue를 통해 건너뛴다.
            continue
        if int(w)<2:
            continue
        sosu=True
        for i in range(2,int(int(w)**0.5)+1): # 소수찾기
            if int(w)%i==0:
                sosu=False
                break
        if sosu:
            count+=1
            
    return count

k진수 변환과 소수 찾기 방식은 유사했습니다.

하지만 w이라는 수의 소수를 찾을 때, w의 제곱근까지만 탐색하면 되기 때문에

for i in range(2,int(int(w)**0.5)+1)

와 같이 표현하여 시간을 줄이는 것이 포인트였습니다.🐤🐤🐤

[다른 사람의 풀이2]

def to_k_number(n, k):  # n을 k진수로 반환
    ret = ""
    while n > 0:
        ret += str(n % k)
        n = n //  k
    return ''.join(reversed(ret))
 
 
def is_prime_num(k):
    if k == 2 or k == 3: return True  # 2 or 3 은 소수
    if k % 2 == 0 or k < 2: return False  # 2의 배수이거나 2보다 작은 값인 경우 소수가 아님
    # 3부터 root(k)까지 2씩 증가하며 확인(3, 5, 7...),
    # 이는 작은 값들의 배수일 때 발생하는 중복을 제거하며 확인(소수 찾기 최적화)
    for i in range(3, int(k ** 0.5) + 1, 2):
        if k % i == 0:
            return False
    return True
 
 
def solution(n, k):
    answer = 0
    k_num = to_k_number(n, k)  # k진수로 반환
    # k_num을 0을 기준으로 분할하여 n을 가져옴
    for n in k_num.split('0'):
        if n == "": continue
        if is_prime_num(int(n)):  # n이 소수인 경우 answer+=1
            answer += 1
    return answer

소수를 찾는 방식이 가장 최적화된 풀이입니다. 2의 배수이면 반드시 소수가 아니기 때문에 조건을 걸어주며

if k % 2 == 0 or k < 2: return False

이후 3 이상부터 제곱근까지 탐색하되 2의 배수를 제외하기 위해

for i in range(3, int(k ** 0.5) + 1, 2):

과 같이 +2씩 증감하게 표현해준 모습입니다.

감사합니다.🐈🐈🐈