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

문제 확인

프로그래머스

나의 풀이

정규 표현식을 활용한 풀이 1 : 에라토스테네스의 체 활용 → 시간 초과

• 작은 진법으로 변환 시, 에라토스테네스의 체로 저장 가능한 범위를 넘기 때문에 테스트 케이스 1을 통과할 수 없다. 
  • 100만을 2진수로 표현하면, 21개의 숫자가 필요한데, 그 이전에 분명 11111111111111...과 같은 숫자가 여러 번 나올 것
• 다양한 패턴을 한번에 확인하기 위해서, 정규 표현식의 Group을 활용했다. 

# 소수 판별
def get_prime(c):
    is_prime = [True] * (c + 1)
    for i in range(2, int(c ** 0.5) + 1):
        if is_prime[i] == True:
            for j in range(i + i, c + 1, i):
                is_prime[j] = False
    return set([i for i in range(2, c + 1) if is_prime[i] == True])
# n 진법 변환
def get_nbase(n, k):
    r_list = ""
    while n:
        q, r = divmod(n, k)
        # 나머지를 모아 n 진법 표현
        r_list += str(r)
        n = q
    return r_list[::-1]

import re

def solution(n, k):
    # 조건에 맞는 소수의 개수
    prime_cnt = 0
    # 소수 판별 위해 미리 소수 확인
    prime_set = get_prime(10**6)
    # n 진법으로 변환
    nbase = get_nbase(n, k)
    # 정규 표현식 패턴
    re_pt = r"(0[1-9]+0)|(^[1-9]+0)|(0[1-9]+$)|([1-9]+)"
    pt = re.findall(re_pt, nbase)
    for p in pt:
        p = "".join(p)
        p = p.replace("0", "")
        if int(p) in prime_set:
            prime_cnt += 1
    
    return prime_cnt

정규 표현식을 활용한 풀이 2 : 소수 판별 활용 → 성공

• 에라토스테네스의 체를 사용하지 않고 소수를 판별했다.

# 소수 판별
def is_prime(n):
    if n <= 1: return False
    for i in range(2, int(n ** 0.5) + 1):
        if n % i == 0: return False
    return True
# n 진법 변환
def get_nbase(n, k):
    r_list = ""
    while n:
        q, r = divmod(n, k)
        # 나머지를 모아 n 진법 표현
        r_list += str(r)
        n = q
    return r_list[::-1]

import re

def solution(n, k):
    # 조건에 맞는 소수의 개수
    prime_cnt = 0
    # n 진법으로 변환
    nbase = get_nbase(n, k)
    # 정규 표현식 패턴
    re_pt = r"(0[1-9]+0)|(^[1-9]+0)|(0[1-9]+$)|([1-9]+)"
    pt = re.findall(re_pt, nbase)
    for p in pt:
        # 그룹 묶기
        p = "".join(p)
        # 0 제거
        p = p.replace("0", "")
        if is_prime(int(p)):
            prime_cnt += 1
    
    return prime_cnt

다른 사람 풀이

• 0을 기준으로 문자열을 분리한 뒤, 남은 숫자가 소수인지 확인했다.
• str.split("문자") : 반복되는 '문자'가 있는 경우, 공백을 반환!

# n을 k진법으로 나타낸 문자열 반환
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

 

[2022 KAKAO Blind Recruitment] Q2. k진수에서 소수 개수 구하기 (C++, Python, Java)