https://school.programmers.co.kr/learn/courses/30/lessons/92335
문제 파악
양의 정수 n을 k진수로 바꾸었을 때, 조건에 맞는 소수가 몇개인지 return해야 한다.
이때 소수는 k진법이 아닌 10진법으로 봤을 때의 소수이다.
조건은 다음과 같다.
1. 소수 양쪽에 0이 있는 경우
2. 소수 왼쪽에 아무것도 없고 오른쪽에 0있는 경우
3. 소수 왼쪽에 0, 오른쪽에 아무것도 없는 경우
4. 소수 양쪽에 아무것도 없는 경우
단 소수는 각 자릿수 어디에도 0을 포함해선 안된다.
ex) 101은 소수지만 이 문제에선 소수로 보지 않는다.
입출력 예시
- n = 437674, k = 3 => result = 3
- n = 110011, k = 10 => result = 2
예시 1
우선 주어진 n을 k진수로 나타내면
211020101011 이다.
여기서 자릿수에 0을 포함하지 않는 소수만 표시하면
211020101011 이다.
사실 0을 기준으로 split하여 소수를 찾으면 무조건 저 4개의 조건 중 하나에 부합한다.
그러니 해결 로직은
1. n을 k 진수로 바꾼다.
2. 0을 기준으로 split한다
3. 소수를 찾아 count +=1 해준다.
가 되겠다.
1. n을 k진수로는 어떻게 바꿀까?
10진수를 k진수로 변환하는 방법은 n을 k로 나누며, 몫은 계속 k로 나누고, 나머지는 계속 나열 한뒤
마지막 몫이 1이 나올때까지 반복한 뒤, 나열한 나머지를 뒤집어 주면 된다.
10을 만약 2진수로 변환한다면
(10,2) => 몫 = 5, 나머지 = 0
(5,2) => 몫 = 2, 나머지 = 1
(2,2) => 몫 = 1, 나머지 = 0
(1,2) => 몫 = 0, 나머지 = 1
(참고로 a//b 할 시, 나머지는 버려진다.)
0101 의 역순 => 1010(2) = 10
def k_num(n,k):
#10진수의 경우 변환할 필요가 없으므로 바로 return 해준다
if k == 10:
return n
else:
new_n = ""
while n > 0:
new_n += str(n % k)
n = n // k
return new_n[::-1]
소수는 어떻게 판별할까?
소수는 1과 n 이외의 숫자로 나눠지지 않으므로, 2부터 n의 루트까지 한 번이라도 나누어 떨어질 때 False를 return 하는 방식으로 판별할 수 있다.
(1도 소수가 아니므로 1보다 작을 경우 역시 False를 return 한다)
def isPrime(n):
if n <= 1:
return False
for i in range(2, int(n**(1/2)+1)):
if n % i == 0:
return False
return True해답 및 풀이
def k_num(n,k):
if k == 10:
return n
else:
new_n = ""
while n > 0:
new_n += str(n % k)
n //= k
return new_n[::-1]
def is_Prime(n):
if n <= 1:
return False
for i in range(2,int(n**(1/2)+1)):
if n % i == 0:
return False
return True
def solution(n, k):
num = k_num(n,k)
cands = str(num).split("0")
answer = 0
for cand in cands:
if cand and is_Prime(int(cand)):
answer += 1
return answer