[Python] 프로그래머스 k진수에서 소수 개수 구하기 (진수 변환, 소수 찾기)

[Python] 프로그래머스 k진수에서 소수 개수 구하기 (진수 변환, 소수 찾기)

문제 링크 : https://school.programmers.co.kr/learn/courses/30/lessons/92335

프로그래머스

 

기록의 이유...

제목이 꽤 길군ㅋ

 

이 문제를 푸는데 아무리 해도 시간 초과가 해결이 안 되더라...

질문하기도 여러 개 보다가 안되어서 포기하고 또 며칠 뒤에 열어서 다시 보고 하다 결국 해결했다.

 

크게 어 나 이거 좀 잘한 것 같은데? + 이건 이렇게 푸는 게 낫겠다 싶은 것 세 가지 요약하자면

1. 진수 변환할 때 deque 사용하기

2. 소수 찾을 때 에라토스테네스의 체가 아닌, 직접 한개씩 확인하는 형태로 가져가기

3. (2-1?) 진수 확인 과정에서의 범위를 제곱근의 값으로 제한하기

이다. 아래에 자세히 적어보겠다...

 

1. 진수 변환할 때 deque 사용하기

흔히 진수 변환할 때 사용하는 방법은 N으로 나눈 나머지를 뒤에서부터 하나씩 더하는 것이다

이 방법을 그대로 활용하기 위해 deque를 사용했다.

문자열 형태로 하나씩 더하자니, 복잡도가 너무 커질 것 같았다.

(관련해서 정리했던 내용 하단 링크 참조)

[Python] Softeer Lv2 - [한양대 HCPC 2023] X marks the Spot (Immutable String)

 

deque의 appendleft를 이용해서 요소를 하나씩 앞에 더해주도록 했고,

최종적으로의 반환은 join을 활용해서 하나의 문자열 형태로 나오게 했다. (437674를 3진수로 > 211020101011)

def changenum(num, under):
    result = deque()
    
    while num > 0:
        result.appendleft(num%under)
        num //= under
        
    return ''.join(map(str, result))

 

2. 소수 찾을 때 에라토스테네스의 체가 아닌, 직접 한개씩 확인하는 형태로 가져가기

PS의 정말 친한 친구인 소수

초중고 다닐 때보다 코테 준비하면서 소수를 더 자주 많이 마주한 것도 같다ㅋ

 

항상 소수 문제가 나왔을 때 하나씩 확인해보려고 하면 시간초과가 걸리니, 에라토스테네스를 써야지!! 가 필수였다.

소수 나왔다 >> 바로 에라토스테네스의 체 구현

 

근데 이번엔 이렇게 해서 풀릴 문제가 아니었다.

계속해서 1번, 11번에서 시간 초과가 나왔다.

 

프로그래머스 자체 질문 게시판을 통해 알아낸 결과...

지나치게 큰 수에 에라토스테네스의 체를 사용하면 효율성이 떨어지기 때문에 시간초과가 발생할 수 있다는 점이었다.

 

그래서 그냥 반복문을 사용해서 소수 여부를 판별하고자 했다.

 

뭔가 명확하게 언제는 에라토스테네스, 언제는 그냥 일반 소수 판별식을 사용해야할까? 에 대한 기준을 생각해보자면

- 범위가 주어지고 그 내에서 소수의 개수를 구할 때는 에라토스테네스의 체

- 값이 매우 크거나, 특정 몇 개의 값들에 대해서 소수 여부를 판별할 때는 일반 소수 판별식

을 사용하는 형태로 가면 되지 않을까? 싶어서 글을 쓰게 됐다.

아무래도 정리해두면 나도 기억에 더 잘 남으니 ㅎㅎ

이런 기준이 아니라 또다른 기준이 있다면, 또는 이런 방식으로 생각하는 게 옳지 않다면 언제든지 알려주세요 ㅎㅎㅎㅎ

 

3. (2-1?) 진수 확인 과정에서의 범위를 제곱근의 값으로 제한하기

에라토스테네스의 체나, 소수 판별을 위해 매번 반복문을 돌릴 때 항상 값의 범위가 하나의 이슈가 된다.

1부터(따지고보면 2부터) 소수 여부를 확인하려는 값까지 전체의 범위로 확인을 하게 될 때,

값의 제곱근 이상의 숫자부터는 확인 여부가 중요하지 않다.

왜냐하면 어떤 값의 약수 중 자기를 제외한 가장 큰 약수는 제곱근의 값이기 때문.

 

그렇기에 소수를 판별하고자 할 때, 즉 특정 값이 어떤 값들의 배수인지 확인하려고 할 때의 범위는 1부터 해당 값의 제곱근까지로 두면 된다.

 

아래는 2번과 3번을 모두 반영한 코드이다.

 

def checkIfPrime(num):
    if num <= 1:
        return False
    
    for i in range(2, int(sqrt(num))+1):
        if num % i == 0:
            return False
        
    return True

 

 

++ python에는 ** 연산자를 확인하여 지수를 적용하는 방법이 있다.

하지만 이는 math.sqrt(x)에 비해 큰 시간복잡도/메모리복잡도를 가지고 있다고 한다. (이유는 나도 잘 모름... 열심히 안 봄)

그렇기에 제곱근을 사용해야 할 때는 math 패키지 내 sqrt 함수를 사용하도록 하자.

 

최종 제출 코드

from collections import deque
from math import sqrt

def changenum(num, under):
    result = deque()
    
    while num > 0:
        result.appendleft(num%under)
        num //= under
        
    return ''.join(map(str, result))

def checkIfPrime(num):
    if num <= 1:
        return False
    
    for i in range(2, int(sqrt(num))+1):
        if num % i == 0:
            return False
        
    return True
    
    

def solution(n, k):
    answer = 0
    
    newnum = changenum(n, k)
    tmparr = newnum.split('0')
    newarr = []
    
    for num in tmparr:
        if len(num):
            newarr.append(int(num))
            
    for num in newarr:
        answer += checkIfPrime(num)
    
    
    return answer

 

아 그리고, 최근에 친구랑 한 문제 가지고 각자 풀고 코드를 공유하는 시간을 가졌는데, 친구는 함수로 각 가능을 구현해두었더라.

함수로 영역을 확실하게 구분해두니 다시 읽을 때도 정말 편하고, 그냥 전체적으로 구성이 다 좋아 보였다. 좋은 습관인 것 같았다.

그래서 나도 이번엔 함수로 각 기능을 구분해 두었는데, 너무 뿌듯하당 ^.^ ㅎㅎ 땡스 투 김뽕나무씨