k지수에서 소수 개수 구하기

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

프로그래머스

---

try1

문제를 읽고 진수 변환과 소수 판단 코드들은 검색해서 가져오면 될 것 같다는 생각이 들음

그래서 코드를 가져온 것들을 이용해 solution을 만듦

 

※ 나의 코드

import string
import math

tmp = string.digits      # 조건이 3 <= k <=10 이므로 0~9까지만 넣어줌
def convert(n, k) :      # 진수 변환 함수
    q, r = divmod(n, k)
    if q == 0 :
        return tmp[r]
    else :
        return convert(q, k) + tmp[r]

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
    checklist = convert(n, k).split('0')
    for check in checklist:
        if check == '' or check == '1':      # 조건에 안맞는 값은 무시하고 for문 진행
            continue
        if primenumber(int(check)):     # 조건에 맞으면 answer에 1을 더해줌
            answer += 1   
      
    return answer

 

문제풀이)

진수변환을 위한 tmp 변수에 string.digists 즉,'0123456789'을 넣음

몫과 나머지를 반환해주는 divmod함수를 이용하여 진수 변환를 하는 convert 함수를 가져옴

소수이면 True, 아니면 False를 반환해서 소수인지 아닌지 판단하는 primenumber 함수를 가져옴

solution 함수에서 convert 함수를 이용하여 진수변환 후 '0'을 기준으로 split를 해서 리스트 형태로 checklist에 넣음

그런 다음 checklist에서 소수인지 아닌지 확인할 필요가 없는 ''과 '1'은 무시하고 for문을 돌리게 하고 나머지 값을 primenumber 함수로 소수인지 아닌지 확인하고 소수이면 answer에 1을 더해줌

 

테스트 결과) - 총합 90.22ms

테스트 1 〉	통과 (89.76ms, 10.4MB)
테스트 2 〉	통과 (0.02ms, 10.4MB)
테스트 3 〉	통과 (0.03ms, 10.4MB)
테스트 4 〉	통과 (0.04ms, 10.4MB)
테스트 5 〉	통과 (0.02ms, 10.3MB)
테스트 6 〉	통과 (0.03ms, 10.3MB)
테스트 7 〉	통과 (0.04ms, 10.3MB)
테스트 8 〉	통과 (0.03ms, 10.2MB)
테스트 9 〉	통과 (0.04ms, 10.3MB)
테스트 10 〉	통과 (0.03ms, 10.4MB)
테스트 11 〉	통과 (0.03ms, 10.4MB)
테스트 12 〉	통과 (0.04ms, 10.3MB)
테스트 13 〉	통과 (0.04ms, 10.4MB)
테스트 14 〉	통과 (0.02ms, 10.3MB)
테스트 15 〉	통과 (0.02ms, 10.4MB)
테스트 16 〉	통과 (0.03ms, 10.3MB)

---

try2

같은 스터디분의 코드를 참고하여 개선함

※ 참고한 코드

import math

def convert(n,k):
    tmp = ''

    while n > 0:
        n, mod = divmod(n, k)
        tmp += str(mod)
    
    return tmp[::-1]

def solution(n, k):
    answer = 0
    
    n_k = convert(n,k)
    n_split = n_k.split('0')
    rm_set = {'', '1'}
    n_split = list(map(int, [i for i in n_split if i not in rm_set]))
    
    for n_s in n_split:
        prime = True
        if n_s == 2 or n_s == 3:
            answer += 1
            continue
        
        if n_s % 2 == 0:          # 짝수일 때 이 후 for문을 돌리지 않으므로 시간이 짧음
            prime = False
            break                 # 오답이 나올 수 있을 것이라고 판단한 부분
            
        max_num = int(math.sqrt(n_s))
        for i in range(3, max_num+1, 2):
            if n_s % i == 0:
                prime = False
                break
                
        if prime:
            answer += 1
    
    return answer

테스트 결과 총합 47.84ms로 가장 빠름

이 코드의 핵심 아이디어는 소수인지 아닌지 판별할 때 예외처리 후 짝수인 경우는 이 후 for문에 들어가지 않으므로 그만큼 속도가 더 빠름

if n_s % 2 == 0:
	prime = False
	break

그런데 프로그래머스 테스트는 통과를 하였지만 이 부분 break에서 오답이 나올 수 있을 거란 생각이 들어서

n = 110805, k = 10일 때를 돌려봄

그 결과 소수는 11과 5 이므로 정답은 2가 나와야 했지만 1이 나옴

그래서 break를 continue로 바꾸고 돌렸더니 올바른 정답이 나옴

이 때, 속도는 약 51ms 정도 나옴

그 다음 개선할 수 있는 부분이 보여서 개선 시도함

※ 개선 후 코드

import string
import math

tmp = string.digits
def convert(n, k) :                 # 진수 변환 방법 바꿈
    q, r = divmod(n, k)
    if q == 0 :
        return tmp[r]
    else :
        return convert(q, k) + tmp[r]

def solution(n, k):
    answer = 0
    
    n_k = convert(n,k)
    n_split = n_k.split('0')
    rm_set = {'', '1'}
    n_split = list(map(int, [i for i in n_split if i not in rm_set]))
    
    for n_s in n_split:
        prime = True
        if n_s == 2 or n_s == 3:
            answer += 1
            continue
        
        if n_s % 2 == 0:
            continue
            
        max_num = int(math.sqrt(n_s))
        for i in range(3, max_num+1, 2):
            if n_s % i == 0:
                break
        else:                  # prime에 True False를 넣어 그것에 따라 answer에 변화를 주기보다는
            answer += 1        # for else 문을 이용함
    
    return answer

 

개선 과정)

제가 해본 진수변환 방법 중 가장 빠른 convert를 사용했고 참고한 코드에서 prime에 True False를 넣지않고 for else문으로 answer 값에 변화를 줌

 

 

테스트 결과) - 총합 45.38ms

테스트 1 〉	통과 (44.96ms, 10.5MB)
테스트 2 〉	통과 (0.03ms, 10.4MB)
테스트 3 〉	통과 (0.03ms, 10.5MB)
테스트 4 〉	통과 (0.03ms, 10.3MB)
테스트 5 〉	통과 (0.03ms, 10.6MB)
테스트 6 〉	통과 (0.02ms, 10.4MB)
테스트 7 〉	통과 (0.03ms, 10.3MB)
테스트 8 〉	통과 (0.03ms, 10.3MB)
테스트 9 〉	통과 (0.03ms, 10.3MB)
테스트 10 〉	통과 (0.03ms, 10.4MB)
테스트 11 〉	통과 (0.03ms, 10.3MB)
테스트 12 〉	통과 (0.02ms, 10.3MB)
테스트 13 〉	통과 (0.03ms, 10.3MB)
테스트 14 〉	통과 (0.03ms, 10.4MB)
테스트 15 〉	통과 (0.03ms, 10.5MB)
테스트 16 〉	통과 (0.02ms, 10.3MB)