[Python] 프로그래머스 코딩테스트 연습 level 2 (k진수에서 소수 개수 구하기)

1. 문제 설명

양의 정수 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 함수를 완성해 주세요.

 

 

2. 제한 조건

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

 

 

 

 

 

3. 내 풀이

- 첫 번째 시도 (정확도 : 88.1)

import string
tmp = string.digits+string.ascii_lowercase
def convert(num, base) :
    q, r = divmod(num, base)
    if q == 0 :
        return tmp[r] 
    else :
        return convert(q, base) + tmp[r]
    
def is_prime_number(x):
    for i in range(2, x):
        if x % i == 0:
            return False
    return True
    
def solution(n, k):
    answer = 0
    num = convert(n,k).split('0')
    for i in num:
        try:
            if int(i) >= 2 and is_prime_number(int(i)):
                answer += 1
        except:
            pass
    return answer

 

1. 숫자를 k진수로 변환해주는 함수 생성

2. 소수 판별 함수 생성

3. n을 k진수로 변환후 0을 기준으로 나누어 리스트 생성

4. 리스트의 원소가 소수이면 answer + 1 하여 총 소수의 개수를 반환

(테스트 케이스 1번 시간 초과)

 

 

import math

# 소수 판별
def primenumber(x):
    for i in range (2, int(math.sqrt(x) + 1)):
    	if x % i == 0:
        	return False
    return True	
    
def solution(n, k):
    answer = 0
    tmp = ''
    if k != 10:
        while n:
            tmp += str(n%k)
            n = n//k
        tmp = tmp[::-1]
    else:
        tmp = str(n)
    tmp_list = tmp.split('0')
    tmp_list = [x for x in tmp_list if x]
    for i in tmp_list:
        if int(i) >= 2 and primenumber(int(i)):
            answer += 1
    return answer

 

 

1. 소수 판별 함수를 제곱근까지만 계산하는 함수로 변경 

2. k진수 변환 : k가 10이 아닌 경우 for문을 사용하여 n을 k로 나누고, 나머지를 tmp에 추가하는 방식 사용

-> 배열을 거꾸로 하여 최종 tmp 

3. k가 10인 경우에는 그대로 n 사용

4. tmp를 0을 기준으로 분할 후 공백 제거하여 리스트 반환

5. 리스트 내의 숫자가 2 이상이고 소수인 경우에만 answer + 1

 

 

 

 

4. 다른 사람 풀이

# 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

1. n을 k진법으로 변환하여 문자열로 반환

2. 소수인지 판별하는 함수 생성 (1인 경우 False 반환)

3. k진법으로 변환된 문자열을 0을 기준으로 분활하고, 빈 문자열에 대한 예외처리를 한 뒤, 소수인 경우 +1