링크: https://school.programmers.co.kr/learn/courses/30/lessons/92335
문제 설명
양의 정수 n이 주어집니다. 이 숫자를 k진수로 바꿨을 때, 변환된 수 안에 아래 조건에 맞는 소수(Prime number)가 몇 개인지 알아보려 합니다.
0P0처럼 소수 양쪽에 0이 있는 경우P0처럼 소수 오른쪽에만 0이 있고 왼쪽에는 아무것도 없는 경우0P처럼 소수 왼쪽에만 0이 있고 오른쪽에는 아무것도 없는 경우P처럼 소수 양쪽에 아무것도 없는 경우- 단,
P는 각 자릿수에 0을 포함하지 않는 소수입니다.- 예를 들어, 101은
P가 될 수 없습니다.
- 예를 들어, 101은
예를 들어, 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
입출력 예
| n | k | result |
|---|---|---|
| 437674 | 3 | 3 |
| 110011 | 10 | 2 |
입출력 예 설명
입출력 예 #1
문제 예시와 같습니다.
입출력 예 #2
110011을 10진수로 바꾸면 110011입니다. 여기서 찾을 수 있는 조건에 맞는 소수는 11, 11 2개입니다. 이와 같이, 중복되는 소수를 발견하더라도 모두 따로 세어야 합니다.
문제풀이
목표: n을 k진수로 바꿨을 때, 문제에서 설명하는 조건에 맞는 소수의 개수를 return
내풀이
문제를 풀기 위해 해야 할 작업은 크게 세 가지인 것 같다.
- n 을 k 진수로 변환.
- 조건에 맞는 숫자 찾기.
- 찾은 숫자가 소수인지 아닌지 판별.
각각의 단계별로 차근차근 해결해보자!
1️⃣ n 을 k 진수로 변환
k 진수로 변환하는 문제 같은 경우는 저번에 비슷한 문제가 있었던 것 같다.
바로, divmod()함수를 활용하는 것. 2, 8, 16 진수는 파이썬에서 제공하는 bin(), oct(), hex() 함수를 사용하면 되지만, 그 외 나머지는 직접 코드로 구현해야 한다.
예를 들어, 문제에서 주어진 437674 를 3진수로 변환한다면 다음과 같다:
def base_n(n, k):
answer = ''
while n > 0:
n, r = divmod(n, k)
answer += str(r)
return answer[::-1]
print(base_n(437674, 3))
결과: 2110201010112️⃣ 조건에 맞는 숫자 찾기
k 진수로 변환이 완료 됐으니, 변환된 숫자에서 주어진 조건에 맞는 소수의 후보를 찾아야 한다.
조건은 다음과 같다:
0P0처럼 소수 양쪽에 0이 있는 경우P0처럼 소수 오른쪽에만 0이 있고 왼쪽에는 아무것도 없는 경우0P처럼 소수 왼쪽에만 0이 있고 오른쪽에는 아무것도 없는 경우P처럼 소수 양쪽에 아무것도 없는 경우- 단,
P는 각 자릿수에 0을 포함하지 않는 소수입니다.
조건을 잘 보면 0이 있든, 없든, 또 어디에 있든 후보가 될 수 있다. 이를 코드로 구현한다면 0 을 기준으로 split 해주면 될 것 같다. 2번까지의 과정을 코드로 구현하면:
def solution(n, k):
# 1번. n을 k진수로 변환
answer = ''
while n > 0:
# n을 k로 나눈 몫과 나머지를 구해 나머지를 answer에 추가.
n, r = divmod(n, k)
answer += str(r)
answer = answer[::-1]
# 2번. 소수 후보 구하기
answer = answer.split('0')
return answer
print(solution(437674, 3))
결과: ['211', '2', '1', '1', '11']3️⃣ 찾은 숫자가 소수인지 판별
이 파트가 가장 어려운 것 같다. 하지만 소수 판별하는 문제는 정말 자주 등장하니 외워두면 좋다. 3번까지해서 전 과정을 다 합쳐 최종코드를 구현하면 다음과 같다.
def solution(n, k):
# 1번. n을 k진수로 변환
answer = ''
while n > 0:
# n을 k로 나눈 몫과 나머지를 구해 나머지를 answer에 추가.
n, r = divmod(n, k)
answer += str(r)
answer = answer[::-1]
# 2번. 소수 후보 구하기
answer = answer.split('0')
# 3번. 후보가 소수인지 아닌지 판별하기
count = 0
for candidate in answer:
if candidate == '': # 후보가 빈 문자열이거나
continue
if int(candidate) < 2: # 2보다 작은 정수라면 다음 후보로 넘어가기
continue
is_prime = True # 소수인지 아닌지 판별할 플래그
for i in range(2, int(int(candidate)**0.5)+1): # 제곱근까지만 탐색해 시간 복잡도 줄이기
if int(candidate) % i == 0: # i 로 나눠진다면 소수가 아니니 플래그를 False로 바꾸고 break
is_prime = False
break
if is_prime: # 전부 다 돌았는데 나눠지는 수가 없다면 소수
count += 1
return count
print(solution(437674, 3))
print(solution(110011, 10))
결과: 3
결과: 2최종코드
def solution(n, k):
# 1번. n을 k진수로 변환
answer = ''
while n > 0:
# n을 k로 나눈 몫과 나머지를 구해 나머지를 answer에 추가.
n, r = divmod(n, k)
answer += str(r)
answer = answer[::-1]
# 2번. 소수 후보 구하기
answer = answer.split('0')
# 3번. 후보가 소수인지 아닌지 판별하기
count = 0
for candidate in answer:
if candidate == '': # 후보가 빈 문자열이거나
continue
if int(candidate) < 2: # 2보다 작은 정수라면 다음 후보로 넘어가기
continue
is_prime = True # 소수인지 아닌지 판별할 플래그
for i in range(2, int(int(candidate)**0.5)+1): # 제곱근까지만 탐색해 시간 복잡도 줄이기
if int(candidate) % i == 0: # i 로 나눠진다면 소수가 아니니 플래그를 False로 바꾸고 break
is_prime = False
break
if is_prime: # 전부 다 돌았는데 나눠지는 수가 없다면 소수
count += 1
return count