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

허준현·2022년 3월 13일
0

CodingTest

목록 보기
8/8
post-thumbnail

취업을 하고나서 그 동안 코딩테스트나 코딩 관련 업무를 하지 않아 주말에 쉬는 겸 LV2 단계 문제를 풀어보면서 감을 익혔다.

문제 출저 : https://programmers.co.kr/learn/courses/30/lessons/92335?language=python3

기본적인 구현문제이며 처음에는 N의 범위가 정해져 백만까지의 소수를 구하면 된다고 생각했지만 원하는 진수로 바꾸면서 백만보다 커지는 경우가 있으므로 에라토스테네스의 체를 이용하기 보다는 그때마다 소수인지 확인해야 한다. 따라서 정확성이 10초를 주어진 것 같다.
또 한 진수도 16진수까지 하게 된다면 알파벳 처리를 어떻게 할지 머리아팠는데 다행이 조건에는 10진수 이하로 나름 대로 배려를 해주었다.
나머지는 문자열을 순회하면서 조건에 부합하는지 확인하면 된다.

from math import sqrt
N=1000000

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

def solution(n, k):
    tmp=''
    while n:
        tmp+=str(n%k)
        n = n//k
    tmp=tmp[::-1]
    answer = 0
    for i in tmp.split('0'):
        if i.isdigit() and prime(int(i)):
            answer+=1
    return answer
profile
best of best

0개의 댓글