About/Python
[Programmers] k진수에서 소수 개수 구하기(Python 풀이) - 2022 KAKAO BLIND RECRUITMENT
김징어
2022. 1. 24. 10:19
https://programmers.co.kr/learn/courses/30/lessons/92335
코딩테스트 연습 - k진수에서 소수 개수 구하기
문제 설명 양의 정수 n이 주어집니다. 이 숫자를 k진수로 바꿨을 때, 변환된 수 안에 아래 조건에 맞는 소수(Prime number)가 몇 개인지 알아보려 합니다. 0P0처럼 소수 양쪽에 0이 있는 경우 P0처럼 소
programmers.co.kr
풀이
1. k진수로의 변환
|
1
2
3
4
5
6
|
def to_k_number(n, k): # n을 k진수로 반환
ret = ""
while n > 0:
ret += str(n % k)
n = n // k
return ''.join(reversed(ret))
|
cs |
입력 값 n이 0보다 큰 값을 가지는 동안 n을 k로 나눈 나머지를 ret에 저장하고, n은 k로 나누어줍니다(나머지는 버림)
위의 동작을 반복하면 ret에는 k진수가 반대로 쌓여있기때문에 이를 reverse하여 반환합니다.
2. 특정 소수 찾기
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
|
def is_prime_num(k):
if k == 2 or k == 3: return True # 2 or 3 은 소수
if k % 2 == 0 or k < 2: return False # 2의 배수이거나 2보다 작은 값인 경우 소수가 아님
# 3부터 root(k)까지 2씩 증가하며 확인(3, 5, 7...),
# 이는 작은 값들의 배수일 때 발생하는 중복을 제거하며 확인(소수 찾기 최적화)
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) # k진수로 반환
# k_num을 0을 기준으로 분할하여 n을 가져옴
for n in k_num.split('0'):
if n == "": continue
if is_prime_num(int(n)): # n이 소수인 경우 answer+=1
answer += 1
return answer
|
cs |
is_prime_num()은 입력 숫자 k가 소수인지 확인하는 함수입니다. 모든 경우를 다 확인할 수 있지만, 빠른 실행을 위해 중복을 제거하여 확인하는 방식으로 소수를 판별하였습니다.
그리고 소수인지 판별하는 조건은 다음과 같은데
- 0P0처럼 소수 양쪽에 0이 있는 경우
- P0처럼 소수 오른쪽에만 0이 있고 왼쪽에는 아무것도 없는 경우
- 0P처럼 소수 왼쪽에만 0이 있고 오른쪽에는 아무것도 없는 경우
- P처럼 소수 양쪽에 아무것도 없는 경우
- 단, P는 각 자릿수에 0을 포함하지 않는 소수입니다.
이는 k진법으로 변환된 숫자를 문자열 변환한 후 0을 기준으로 분할하여 각 숫자를 10진수라고 가정하여 소수인지 판별하면 해결할 수 있습니다.
예를들어 n=4376741, k=3인 경우 k진수는 211020101011입니다.
이를 문자열로 변환한 후 0을 기준으로 분할하게되면 다음과 같습니다.
|
1
2
|
"211020101011".split('0')
['211', '2', '1', '1', '11']
|
cs |
이를 하나씩 가져와 is_prime_num() 함수에서 소수인지 판별한 후 소수인 경우 count를 추가하면 됩니다.
전체 소스 코드
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
|
def to_k_number(n, k): # 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 # 2 or 3 은 소수
if k % 2 == 0 or k < 2: return False # 2의 배수이거나 2보다 작은 값인 경우 소수가 아님
# 3부터 root(k)까지 2씩 증가하며 확인(3, 5, 7...),
# 이는 작은 값들의 배수일 때 발생하는 중복을 제거하며 확인(소수 찾기 최적화)
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) # k진수로 반환
# k_num을 0을 기준으로 분할하여 n을 가져옴
for n in k_num.split('0'):
if n == "": continue
if is_prime_num(int(n)): # n이 소수인 경우 answer+=1
answer += 1
return answer
|
cs |
