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

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

프로그래머스

---

1. 접근 방식

• n을 k진수로 바꾸면서 문자열로 반환하자.

위 그림은 10진수 n = 532를 3진수로 바꾸는 과정이다. 532를 3으로 나눈 나머지들이 모여서 3진수로 표현된다. 따라서 n을 k진수로 바꾸는 과정은 n이 0보다 클 동안 (1) n을 k로 나눈 나머지를 저장하고 (2) n을 k로 나누는 작업을 반복하는 것이다.

단, 이때 효율성을 위하여 k가 10진수라면 n을 문자열로 변환하여 바로 반환한다.

 

• k진수로 변환된 문자열 값을 0을 기준으로 나누자.

(1) 0P0 (2) P0 (3) 0P (4) P라는 4가지 조건에 해당하는 모든 P를 구하는 방법은 결국 '201201'을 '0'을 기준으로 split( )하는 것이다. 단, '20100'.split('0')의 결과는 [ '2', '1', '', '']임에 유의해야 한다. '0'으로 쪼갠 결과가 빈 문자열이라서 ''이 추가되기 때문이다.

 

• 소수 판정법에서 시간을 단축하자.

def is_prime(n):
    for i in range(2, n):
        if n % i == 0:
            return False
    return True

위의 코드처럼 n = 101이 소수인지 판정하기 위해서 2, 3, 4, 5, ..., 97, 98, 99, 100으로 101을 나누는 방식은 시간이 너무 오래 걸린다. 이 문제에서 n은 최대 백 만까지 가능하기 때문에 위 코드대로라면 시간 초과가 발생할 위험이 있다.

따라서 2부터 n-1까지 나누는 방식 대신 2부터 (int(루트 n) + 1)까지 나누는 방식을 선택한다. 즉, 2부터 (10.xxx + 1) = 11까지 나누어보는 것만으로도 n이 소수인지 아닌지를 판정할 수 있다.

 

 

2. 정답 코드

def change(n, k):
    if k == 10:
        return str(n)
    
    result = ''
    while n:
        result += str(n%k)
        n //= k

    return result[::-1]

def is_prime(n):
    import math

    if n == 1:
        return False
    
    for i in range(2, int(math.sqrt(n)) + 1):
        if n % i == 0:
            return False
        
    return True
    
def solution(n, k):
    n = change(n, k)
    ps = [1 for p in n.split('0') if p and is_prime(int(p))]
            
    return sum(ps)