[python] programmers - k진수에서 소수 개수 구하기

programmers - k진수에서 소수 개수 구하기

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

프로그래머스

자세한 설명은 위의 링크를 확인하세요.

 

문제 설명

예를 들어, 437674을 3진수로 바꾸면 211020101011입니다. 여기서 찾을 수 있는 조건에 맞는 소수는 왼쪽부터 순서대로 211, 2, 11이 있으며, 총 3개입니다. (211, 2, 11을 k진법으로 보았을 때가 아닌, 10진법으로 보았을 때 소수여야 한다는 점에 주의합니다.) 211은 P0 형태에서 찾을 수 있으며, 2는 0P0에서, 11은 0P에서 찾을 수 있습니다.

정수 n과 k가 매개변수로 주어집니다. n을 k진수로 바꿨을 때, 변환된 수 안에서 찾을 수 있는 위 조건에 맞는 소수의 개수를 return 하도록 solution 함수를 완성해 주세요.

 

문제풀이

문제는 간단합니다. 진수변환과 소수판단만 할 수 있다면 쉽게 해결할 수 있습니다.

하지만 소수 판단을 O(n) 의 시간복잡도로 작성하면, int overflow가 발생하기때문에 O(root(n))의 시간 복잡도로 작성해야합니다. 이것에 주의해서 코드를 작성해야할 것 같습니다.

 

먼저 첫번째로 작성한 코드는 아래와 같습니다.

def is_prime(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):     answer = 0        res = []     while n > 0:         m = n % k         res.append(m)         n = n // k          res.reverse()     num = 0     for i in res:         if i != 0:             num = num * 10             num = num + i         else:             if is_prime(num) and num != 0:                 answer += 1                 print("발견된 소수는 " + str(num))             num = 0                  if is_prime(num) and num != 0:         answer += 1         print("발견된 소수는 " + str(num))              return answer

아마 1학년때 c언어로 이런식으로 풀던 버릇이 있어서 제일 1차적인 풀이는 위의 코드처럼 작성했습니다.

조금 더 간단하게 구현하면 아래 처럼도 가능합니다.

def is_prime(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):     answer = 0     res = ''     while n > 0:         m = n % k         res += str(m)         n = n // k     res = "".join(reversed(res))     res = res.split('0')     for num in res:         if is_prime(num):             answer += 1                  return answer

 

알게된 점

문자열을 뒤집는 방법

string = "hello world"

1. 슬라이싱

string = string[::-1]

start:end:step 에서 ::-1 과 같이 작성하면, 문자열을 거꾸로 슬라이싱함.

 

2. "".join(reversed(string))

 

3. O(root(n)) 의 소수판별

def is_prime(n):     if n <= 1: return False     i = 2     while i*i <= n:         if n%i == 0: return False         i += 1     return True

i * i <= n 이 조건을 통해 시간복잡도를 줄이는건데 생각해보면 단순하다.

n의 약수는 무조건 sqrt(N)의 범위에 존재하게 되는 원리이다.

 

어떤 수 n을  a * b 라고 표현했을때 a = 1 , 2, 3, ... , root(n)  * b = n , n/2 , n/3 , . .. . root(n)으로 나타낼 수 있다.

즉 a가 커지면 b가 작아지고, b가 커지면 a가 작아지는 반비례 관계에 있으므로

제곱근 값안에 항상 약수가 존재하게 되는 것이다.

 

따라서 n의 제곱근까지의 수들만 조사하면 빠르게 소수판별을 할 수 있다.