프로그래머스 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

입출력 예 설명

입출력 예 #1

문제 예시와 같습니다.

입출력 예 #2

110011을 10진수로 바꾸면 110011입니다. 여기서 찾을 수 있는 조건에 맞는 소수는 11, 11 2개입니다. 이와 같이, 중복되는 소수를 발견하더라도 모두 따로 세어야 합니다.

문제가 잘 안풀린다면😢

힌트가 필요한가요? [코딩테스트 연습 힌트 모음집]으로 오세요! → 클릭

풀이

• 이거 문제 읽자마자 무지성 코딩하고, 소수 판별하는 부분은 인터넷에서 가져옴.
• 먼저 2진수로 바꾸고, 문자열로 변환 -> 뒤집어 주기.
• 정규표현식으로 0 기준으로 split 해서 리스트로 만들기 + 문자열이니까 int로 변환
• 소수인지 판별. isitPrime() 함수 사

import re

def isitPrime(k):
    if k==2 or k==3: return True
    if k%2==0 or k<2: return False
    for i in range(3, int(k**0.5)+1, 2):
        if k%i==0:
            return False
    return True

def solution(n, k):
    kn = 0           # n을 k진수로 바꾸기
    while n > 0:
        kn += n % k
        kn *= 10
        n //= k
    skn = str(kn)
    skn = skn[::-1]
    numbers = re.split(r'[0]', skn)
    numbers = [int(n) for n in numbers if n != '' and n != '1'] #    print(numbers)
    kn = 0
    for n in numbers:
        if isitPrime(n):
            kn += 1
    return kn
    
정확성  테스트
테스트 1 〉	통과 (48.34ms, 10.5MB)
테스트 2 〉	통과 (0.07ms, 10.5MB)
테스트 3 〉	통과 (0.09ms, 10.5MB)
테스트 4 〉	통과 (0.11ms, 10.4MB)
테스트 5 〉	통과 (0.10ms, 10.3MB)
테스트 6 〉	통과 (0.07ms, 10.4MB)
테스트 7 〉	통과 (0.08ms, 10.4MB)
테스트 8 〉	통과 (0.07ms, 10.4MB)
테스트 9 〉	통과 (0.08ms, 10.5MB)
테스트 10 〉	통과 (0.10ms, 10.3MB)
테스트 11 〉	통과 (0.08ms, 10.4MB)
테스트 12 〉	통과 (0.07ms, 10.4MB)
테스트 13 〉	통과 (0.08ms, 10.4MB)
테스트 14 〉	통과 (0.07ms, 10.5MB)
테스트 15 〉	통과 (0.07ms, 10.5MB)
테스트 16 〉	통과 (0.07ms, 10.5MB)

• 고수의 풀이, 반값, 아니 속도가 반.

import math
def solution(n, k):
    x = ''
    while n:
        a = n%k
        x = str(a) + x
        n = n//k
    answer = 0
    A = x.split('0')
    for prime in A:
        if not prime.isdigit(): continue
        prime = int(prime)
        if prime in [1,4,6,8,9,10,12,14,15]: continue
        if prime in [2,3,5,7,11,13]:
            answer += 1
            continue

        for i in range(3,int(math.sqrt(prime))+1,2):
            if prime%i ==0: break
        else:
            answer += 1
    return answer
    
정확성  테스트
테스트 1 〉	통과 (45.32ms, 10.4MB)
테스트 2 〉	통과 (0.03ms, 10.4MB)
테스트 3 〉	통과 (0.04ms, 10.5MB)
테스트 4 〉	통과 (0.03ms, 10.4MB)
테스트 5 〉	통과 (0.03ms, 10.4MB)
테스트 6 〉	통과 (0.02ms, 10.4MB)
테스트 7 〉	통과 (0.03ms, 10.4MB)
테스트 8 〉	통과 (0.02ms, 10.5MB)
테스트 9 〉	통과 (0.03ms, 10.4MB)
테스트 10 〉	통과 (0.03ms, 10.5MB)
테스트 11 〉	통과 (0.03ms, 10.4MB)
테스트 12 〉	통과 (0.03ms, 10.4MB)
테스트 13 〉	통과 (0.03ms, 10.6MB)
테스트 14 〉	통과 (0.03ms, 10.4MB)
테스트 15 〉	통과 (0.03ms, 10.5MB)
테스트 16 〉	통과 (0.03ms, 10.6MB)

• 더 빠른 것 같은데 테스트 1번만 느린 방식

def conv(n, k):
    s = ''
    while n:
        s += str(n%k)
        n //= k
    return s[::-1]

# n이 소수인지 판정
def isprime(n):
    if n <= 1: return False
    i = 2
    while i*i <= n:
        if n%i == 0: return False
        i += 1
    return True

def solution(n, k):
    s = conv(n,k)
    cnt = 0
    for num in s.split('0'):
        if not num: continue # 빈 문자열에 대한 예외처리
        if isprime(int(num)): cnt += 1
    return cnt
    
테스트 1 〉	통과 (140.48ms, 10.2MB)
테스트 2 〉	통과 (0.03ms, 10.3MB)
테스트 3 〉	통과 (0.02ms, 10.4MB)
테스트 4 〉	통과 (0.03ms, 10.4MB)
테스트 5 〉	통과 (0.02ms, 10.4MB)
테스트 6 〉	통과 (0.03ms, 10.4MB)
테스트 7 〉	통과 (0.04ms, 10.3MB)
테스트 8 〉	통과 (0.02ms, 10.3MB)
테스트 9 〉	통과 (0.02ms, 10.3MB)
테스트 10 〉	통과 (0.02ms, 10.2MB)
테스트 11 〉	통과 (0.04ms, 10.2MB)
테스트 12 〉	통과 (0.03ms, 10.4MB)
테스트 13 〉	통과 (0.02ms, 10.4MB)
테스트 14 〉	통과 (0.04ms, 10.3MB)
테스트 15 〉	통과 (0.02ms, 10.4MB)
테스트 16 〉	통과 (0.02ms, 10.4MB)

끝.

정규표현식 참고한 블로그

https://jh2021.tistory.com/7

정규표현식(Regular Expression) with 파이썬 . ? + *기호 re.compile(), re.findall(), re.sub() (1)

https://jh2021.tistory.com/8?category=967585 

정규표현식(Regular Expression) with 파이썬 . ? + *기호 re.compile(), re.findall(), re.sub() (2)