2022.02.27 [프로그래머스] (python 파이썬) k진수에서 소수 개수 구하기

 

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

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

---

풀이

• 이 문제는 우선 주어진 숫자n을 k진수로 바꿔야 한다.
• 그래서 n을 k로 나눈 나머지를 temp에 문자로 저장하여 n을 k진수로 바꾼 값을 구했다.
• 이때 위의 방식대로 저장하면 k진수의 역수로 저장되기 때문에 12번째 줄과 같이 문자열을 뒤집어준다.
• 문제의 조건을 보면 소수를 판별할 수를 뽑을 때, 0이 껴있지 않아야 한다.
• 그래서 문자열을 '0'으로 나눈 값을 arr배열에 저장했다. 만약 k진수로 바꾼 수에 0이 연속해서 나오면 arr배열에 ''과 같이 빈공간도 저장된다.
• 빈공간을 없앨 때, 1은 소수가 아니기 때문에 빈공간과 1이 아닐 때 수를 int형으로 바꿔 arr2에 저장한다.
• 이제 arr2에 담긴 숫자를 소수인지 아닌지 판별하여 answer배열에 담았다.
• 여기서 for문의 범위가 math.sqrt(i)+1인 이유는 i의 제곱근 까지만 확인하면 소수인지 알 수 있기 때문이다.
• 예를 들면 i가 16일때, 약수는 [1,2,4,8,16]이 된다. 약수를 보면 i의 제곱근인 4를 기준으로 대칭인 것을 확인할 수 있다.

 

import math
 
 
def solution(n, k):
    answer = []
    temp = ''
    #n을 k진수로 바꾸기 위한 while문
    while n > 0:
        temp += str(n % k)
        n //= k
    #위의 방식으로 k진수를 구하면 반대로 구해져서 문자열을 뒤집어줌
    temp = temp[::-1]
    #소수를 구할 때, 0이 껴있으면 안되므로 0으로 문자열을 잘라줌
    arr = list(temp.split('0'))
    arr2 = []
    for i in arr:
        #만약 0이 연속해서 나오면 ''과 같은 빈공간이 저장될 수 있으므로
        #빈공간과 소수가 아닌 1은 제외하고 arr2배열에 int형으로 저장
        if i != '' and i != '1':
            arr2.append(int(i))
    #저장된 숫자의 소수 판별
    for i in arr2:
        check = True
        for j in range(2, int(math.sqrt(i)) + 1):
            if i % j == 0:
                check = False
                break
        if check:
            answer.append(i)
 
    return len(answer)