[Programmers] k진수에서 소수 개수 구하기

출처

---

 

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

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

 

 

 

문제

---

 

 

제한사항

---

 

 

풀이 및 코드

---

문제 조건만 보면 1) 0P0일 때 2) P0일 때 3) 0P일 때 4) P는 각 자릿수에 0을 포함하지 않을 때로

뭔가 복잡해 보이는 것 같다. 그러나 자세히 보면 결국 이 조건들은 0을 가지고 숫자를 나누라는 얘기이다.

따라서, 이 문제에서 크게 해야할 일들은

 

1. k진수로 n을 변환
2. 0을 기준으로 변환한 값을 나누기
3. 각 값의 소수 여부 판별

이렇게 3개로 나눌 수 있다.

 

그러므로 k진수 변환을 위해 유클리드 호제법을,

0을 기준으로 값을 나누기 위해 split() 함수를,

소수 판별을 위해 소수의 성질을 이용해서 다음과 같이 구현하였다.

 

k진수 변환 과정에서 추후 split() 함수를 쓰므로 굳이 형변환 하지 않고 String으로 반환하였고,

0을 기준으로 split()했을 때, 발생하는 공백을 제거하기 위해 리스트 컴프리헨션을 사용하였다.

소수 판별에서는 에라토스테네스의 체를 이용할까 했지만, 제한조건의 범위가 크지 않다고 판단하여 해당 수의 제곱근까지만 for문을 돌며 나누어 떨어지는 수가 있는지 없는지를 가지고 소수를 판별했다.

 

def convert(n, k):
    convertedN = ""
    while (n >= 1):
        convertedN = str(n%k) + convertedN
        n //= k
    return convertedN

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

def solution(n, k):
    convertedN = convert(n, k)
    numList = convertedN.split("0")
    numList = [int(x) for x in numList if x != ""]
    
    answer = 0
    for num in numList:
        if num == 1: continue
        if prime(num):
            answer += 1
            
    return answer