[프로그래머스]Lv2. k진수에서 소수 개수 구하기(Python)

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

프로그래머스

 

문제 접근

 

<문제 조건 정리>

1. 0P0처럼 소수 양쪽에 0이 있는 경우

2. P0처럼 소수 오른쪽에만 0이 있고 왼쪽에는 아무것도 없는 경우

3. 0P처럼 소수 왼쪽에만 0이 있고 오른쪽에는 아무것도 없는 경우

4. P처럼 소수 양쪽에 아무것도 없는 경우

 

단, P는 각 자릿수에 0을 포함하지 않는 소수 101은 P가 될 수 없음 

 

사고 흐름..

1. 해당 숫자를 k진법으로 변환 => 좀 익히자..

2. 0을 기준으로 숫자를 분리한다. => split()

3. 문자열을 숫자로 변환하여 해당 숫자가 소수인지 판단 => int(), 소수 판별 함수 다시 공부

4. 소수라고 판단되면 cnt += 1

 

코드

# 소수 판별 함수
def is_prime_number(x):
    for i in range(2, int(x**(0.5))+1):
        if x % i == 0:
            return False
    return True
    
def solution(n, k):
    word = ""    # 결과를 저장할 빈 문자열 초기화 
    
    while n:
        word = str(n % k) + word    # 10진수까지의 변환만 가능
        n //= k
    
    word = word.split("0")
    cnt = 0
    
    for w in word:
        if len(w) == 0:
            continue
        if int(w) < 2:
            continue
        
        if is_prime_number(int(w)):
            cnt += 1

    return cnt

 

문제 회고 

 

소수 판별 함수로 개선된 소수 판별 함수로 사용하지 않고 범위를 2부터 x까지 할 경우에 테케 1이 통과하지 못하니 웬만하면 개선된 알고리즘으로 작성하고, 진수 변환하는 코드를 숙지해 놓자