[Python/Kakao2022]

정나린·2022년 3월 7일

kakao2022 python 코딩테스트

문제

1. 난이도: 프로그래머스 Level 2

2. 문제요약:

양의 정수 n과 k가 주어진다.
10진수 n을 k진수로 변환한다.
변환된 수 안에 아래 조건에 맞는 소수(P)가 몇 개인지 반환하라.
- 0P0처럼 소수 양쪽에 0이 있는 경우
- P0처럼 소수 오른쪽에만 0이 있고 왼쪽에는 아무것도 없는 경우
- 0P처럼 소수 왼쪽에만 0이 있고 오른쪽에는 아무것도 없는 경우
- P처럼 소수 양쪽에 아무것도 없는 경우
- (단, P는 각 자릿수에 0을 포함하지 않는 소수)
P가 소수인지는 십진수 기준으로 판단한다.
- P = 211 이라면, 이백십일(211)이 소수인지를 판단하는 것이다.

3. 문제핵심: for문을 사용한 진법변환, 소수검사

4. 제한사항: 정확도 검사 10초 이내

내 코드

import math
def solution(n, k):
    nk = ''
    answer = 0
    
    while n // k != 0:
        nk = str(n%k) + nk
        n = n // k
        
    if n != 0:
        nk = str(n) + nk
        
    nk_list = nk.split('0')

    
    for n in nk_list:
        isPrime = True
        
        if n == '1':
            isPrime = False    
        elif n != '':
            for i in range(2, int(math.sqrt(int(n)))+1):
                if int(n) % i == 0:
                       isPrime = False
        else:
             isPrime = False           
            
        if isPrime:
            answer += 1 
            
    return answer

1. 진수변환

10진수 n을 k진수로 변환하는 법: 몫이 0이될 때까지 n을 k로 나누고 각 과정에서의 나머지를 역순으로 적는다.
while문의 조건으로 몫이 0일 때 나머지가 포함되지 않으므로 잊지 말고 이 부분 추가한다.

if n != 0:
        nk = str(n) + nk

2. 0으로 숫자 구분

0기준으로 숫자 구분 -> 특정 기준으로 구분한다.
string.split()을 사용한다.

3. 소수검사

n이 소수이다 == n의 약수가 1과 자기자신(n) 뿐이다.

for문의 범위:
- range(2, int(n))도 맞지만,
- range(2, int(math.sqrt(int(n))+1))으로 불필요한 반복을 줄인다.
- n의 제곱근까지도 나누어떨어지지 않는다면 n은 소수이기 때문이다.

이상 코드

def to_k_number(n, k):  
   ret = ""
   while n > 0:
       ret += str(n % k)
       n = n //  k
   return ''.join(reversed(ret))

def is_prime_num(k):
   if k == 2 or k == 3: return True  
   if k % 2 == 0 or k < 2: return False 
   
   for i in range(3, int(k ** 0.5) + 1, 2):
       if k % i == 0:
           return False
   return True

def solution(n, k):
   answer = 0
   k_num = to_k_number(n, k)  
   for n in k_num.split('0'):
       if n == "": continue
       if is_prime_num(int(n)):  
           answer += 1
   return answer

(출처: https://kimjingo.tistory.com/147?category=946327)