[프로그래머스] k진수에서 소수 갯수 구하기 문제풀이 python

🐒 문제

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

✍ 나의 풀이

def sosu(x):
    if x <= 1:
        return False
    for i in range(2,int(x**0.5)+1):
        if x%i == 0:
            return False
    return True

def solution(n, k):
    answer = 0
    kbase = ''
    
    while n:
        kbase += str(n%k)
        n //= k
    kbase = kbase[::-1].split('0')
    kbase = [int(i) for i in kbase if i != '']
    
    # 소수찾기 알고리즘
    for i in kbase:
        if sosu(i):
            answer += 1
    
    return answer

---

🧠 문제 이해

문제 풀이를 위해서 3단계로 접근했다.

1. 주어진 10진수 n을 k진수로 변환하기
2. k진수에서 0이 아닌 숫자들 꺼내오기
3. 꺼내온 숫자들 중에 소수가 몇 개인지 구하기

1. 주어진 10진수 n을 k진수로 변환하기

kbase = ''
    
while n:
	kbase += str(n%k)
	n //= k

kbase = kbase[::-1] #.split('0')

2. k진수에서 0 이 아닌 숫자들 꺼내오기

kbase = kbase[::-1].split('0')
kbase = [int(i) for i in kbase if i != '']

split() 메소드를 이용해 '0'을 기준으로 문자열들을 갈라 리스트에 넣는다.

그 다음 리스트에 들어온 숫자들을 정수형으로 변환시킨다.
split()메소드 때문에 ''가 리스트에 들어있는데, ''는 걸러낸다.

3. 꺼내온 숫자들 중에 소수가 몇 개인지 구하기

def sosu(x):
    if x <= 1:
        return False
    for i in range(2,int(x**0.5)+1):
        if x%i == 0:
            return False
    return True
    
for i in kbase:
        if sosu(i):
            answer += 1

return answer

소수인지를 판별하는 함수 sosu에서 True를 리턴받으면 찾은 소수 갯수를 하나 올려주고, False를 리턴받으면 넘어간다.

나는 처음에 소수인지 확인할 숫자가 많기 때문에 에라토스테네스의 체를 통해서, kbase리스트의 최대값까지 소수여부를 미리 찾아놓으려 했는데,

이렇게 하면 시간초과가 발생하거나 런타임에러가 발생한다.

---

문제 조건은 아래와 같다.

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

https://blog.encrypted.gg/1026

위 블로그의 내용처럼 n=797161, k=3 일때 n의 k진수는

'1111111111111'

이며, 10진수에서 2**40과 근사한 값이다.

지나치게 큰 값에 에라토스테네스의 체를 사용하면 효율성이 떨어진다.

따라서 개별적으로 하나씩 소수여부를 확인해야한다.

소수 확인 알고리즘

---

처음 코드(1번, 11번 테케 런타임 에러)

def solution(n, k):
    answer = 0
    kbase = ''
    
    while n:
        kbase += str(n%k)
        n //= k
    kbase = kbase[::-1].split('0')
    kbase = [int(i) for i in kbase if i != '']

    maxk = max(kbase)
    
    arr = [True] * (maxk+1)
    arr[0], arr[1] = False, False

	# 에라토스테네스의 체
    for i in range(2,int((maxk+1)**1/2)+1):
        if arr[i]:
            multi = 2
            while i*multi <= maxk:
                arr[i*multi] = False
                multi += 1
                
    for i in kbase:
        if arr[i]:
            answer += 1
    
    return answer