[Programmers/파이썬]프로그래머스(Lv.2) k진수에서 소수 개수 구하기 문제풀이

문제 설명

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

---

제한사항

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

---

입출력 예

nkresult

437674	3	3
110011	10	2

 

 

---

문제 푸는데 걸린 시간

33분

 

사고 흐름

문제 이름에서 나와있듯이 소수를 구하는게 핵심인 문제구나

-> 문제 요구하는 소수 조건이 길어보이지만 쉽게 생각하면 0을 기준으로 숫자를 나눈다고 쉽게 생각하자

-> 먼저 주어진 숫자를 k진수로 바꾸고

-> 0을 기준으로 숫자를 나누고 (공백 처리를 위한 코드 추가..)

-> 각 숫자가 소수인지 판별해야겠다

 

문제 핵심과 알고리즘

진수로 바꾸는 알고리즘과 효율적인 수소 판별 알고리즘

import math

def solution(n, k) :
    answer=0
    k_binary = make_k(n, k).split("0")

    for i in k_binary :
       if i!='' and check_prime(int(i)) :
           answer+=1
        
    return answer

def make_k(n, k) :
    string = ""
    while n>0 :
        string+=str(n%k)
        n=n//k

    return string[::-1]

def check_prime(n) :
    if n==1 :
        return False
        
    for i in range(2, int(math.sqrt(n) + 1)) :
        if n%i==0 :
            return False
    return True

 

문제 풀면서 헤맸던 부분

1. 0을 기준으로 문자열 나누는 다른 방법은?

  나는 spilt()으로 쪼갰지만 아직 정규표현식으로 문자열 다루는게 익숙하지 않아서 공부가 필요하다.

2. 소수 판별 알고리즘

  처음에는 check_prime 함수에서 for문 범위를 (2, n)으로 설정하고 문제를 풀었는데 1번이 시간 초과가 났다. 생각해 보니 시간 초과가 날 부분이 이 부분밖에 없어서 수정했지만,, 좋은 방법을 생각하지 못했고 결국 구글링해서 문제를 해결했다. 그냥 이 부분은 암기하자! 

 

다른 사람 코드 참고하며 배운점

다른 사람들도 비슷하게 풀었다. 

 

<개념 정리>

1. 소수 판별 알고리즘

소수: 1과 자기 자신만을 약수로 갖는 수

  1) 해당하는 숫자까지 모든 수로 나눠서 판단 -> 시간복잡도 O(N)

def is_prime1(n) :
	for i in range(2, n) :
    	if n%i==0 :
        	return False
    return True

  2) 해당 숫자의 절반까지만 확인 -> 시간복잡도 O(N)

숫자의 절반을 초과하는 숫자로 나눴을 때 나머지가 0이 되는 숫자는 나올 수 없음

def is_prime2(n) :
	for i in range(2, n/2) :
    	if n%i==0 :
        	return False
    return True

  3) 해당 숫자의 √N 까지 확인 -> 시간복잡도 O(√N)

√N은 해당 숫자의 약수들의 중간값으로, √N을 기준으로 약수들이 서로 대칭돼있다. 따라서 중간값인 √N를 기준으로 한 쪽만 검사하면 된다. 

def is_prime3(n) :
	for i in range(2, int(math.sqrt(n)) + 1) :
    	if n%i==0 :
        	return False
    return True

 

 

(2023/03/15에 다시 풀어본 코드)

import re
import math
def solution(n, k) :
    answer=0
    string=re.findall('[1-9]+', make_k(n, k))
    for s in string :
        if isprime(int(s)) :
            answer+=1
        
    return answer

def make_k(n, k) :
    string=''
    while n :
        string+=str(n%k)
        n=n//k
    return string[::-1]
        
def isprime(num) :
    if num==1 :
        return False
    for i in range(2, int(math.sqrt(num))+1) :
        if num%i==0 :
            return False
    return True

처음 풀었을 때와 비슷하다. 하지만 문자열 다루는게 훨씬 능숙해졌고, 진수로 바꾸는 알고리즘이나 소수 판별하는 알고리즘도 익숙해서 훨씬 수월하게 풀이할 수 있었다.