[Python/프로그래머스/Level2/KAKAO] k진수에서 소수 개수 구하기

문제

양의 정수 n이 주어집니다. 이 숫자를 k진수로 바꿨을 때, 변환된 수 안에 아래 조건에 맞는 소수(Prime number)가 몇 개인지 알아보려 합니다.

• 0P0처럼 소수 양쪽에 0이 있는 경우
• P0처럼 소수 오른쪽에만 0이 있고 왼쪽에는 아무것도 없는 경우
• 0P처럼 소수 왼쪽에만 0이 있고 오른쪽에는 아무것도 없는 경우
• P처럼 소수 양쪽에 아무것도 없는 경우
• 단, P는 각 자릿수에 0을 포함하지 않는 소수입니다.
  • 예를 들어, 101은 P가 될 수 없습니다.

예를 들어, 437674을 3진수로 바꾸면 211020101011입니다. 여기서 찾을 수 있는 조건에 맞는 소수는 왼쪽부터 순서대로 211, 2, 11이 있으며, 총 3개입니다. (211, 2, 11을 k진법으로 보았을 때가 아닌, 10진법으로 보았을 때 소수여야 한다는 점에 주의합니다.) 211은 P0 형태에서 찾을 수 있으며, 2는 0P0에서, 11은 0P에서 찾을 수 있습니다.

정수 n과 k가 매개변수로 주어집니다. n을 k진수로 바꿨을 때, 변환된 수 안에서 찾을 수 있는 위 조건에 맞는 소수의 개수를 return 하도록 solution 함수를 완성해 주세요.

제한 사항

• 1 ≤ n ≤ 1,000,000
• 3 ≤ k ≤ 10

입출력 예시

n	k	result
437674	3	3
110011	10	2

나의 풀이

def convert(n, q) : // n진수 변환 함수
    rev_base = ''
    while n > 0:
        n, mod = divmod(n, q)
        rev_base += str(mod)
    return rev_base[::-1] 

def getPrimeNum(n): // 소수 찾기 함수
    if n == 1 :
        return False
    elif n == 2 :
        return True
    m = int(n ** 0.5) + 1
    for i in range(2, m):
        if n % i == 0 :
            return False
    return True

def solution(n, k): // K진수에서 소수 개수 구하기 함수
    n = convert(n, k)
    lists = str(n).split('0')
    lists = list(filter(lambda x: x != '', lists))
    lists = list(map(lambda x: getPrimeNum(int(x)), lists))
    return lists.count(True)

 

  n으로 받은 숫자를 k진수로 바꿔주는 과정이 먼저 필요하다. 그래서 k진수화 시켜주는 함수를 conver(n, q)로 제작하였다. 파이썬 함수인 divmod를 이용하였다. divmod는 몫과 나머지를 구해주는 함수이다. 예로 n이 437674였고 k가 3이었다면 변환된 값은 211020101011이 된다.

  k진수로 변환한 후에 조건에 맞는 소수 개수를 찾아야한다. 여기서는 4개의 조건을 줬다. 조건을 보면 0을 기준으로 0이 양쪽에 있는지 / 0이 오른쪽에 있는지 / 0이 왼쪽에 있는지 / 0이 하나도 없는지 (물론 소수인 경우일 때)로 나눠지는 것을 알 수 있다. 그렇기 때문에 먼저 0을 기준으로 숫자를 나눠주었다. 여기서 가끔 변수가 있었는데, 0이 연속으로 나올 경우에 ''가 배열에 삽입될 수 있다. 그렇기 때문에 빈 ''값을 제거해주기 위해 filter 고차함수를 사용하였다. 위의 예로 들어보면 배열은 [211, 2, 1, 1, 11]이 된다.

  이다음에는 이 배열에 있는 숫자들을 소수가 맞는지 아닌지로 판단해주기 위해 getPrimeNum(n) 함수를 제작해주었다. 완전 탐색을 이용했다. 여기서 제일 포인트는 제곱근까지 검사를 해주는것이다. 전체 N까지 검사를 해줄 수도 있지만 그러면 시간 초과가 날 수 있다. 제곱근까지만 검사를 해도 충분하다. 배열을 모두 소수인지 판단해준다면 [T, T, F, F, T] 가 나오게 된다.

이제 이 소수 판별 배열에서 True 의 개수를 구해주면 된다.

---

2022 KAKAO BLIND RECRUITMENT - k진수에서 소수 개수 구하기

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