🔴 문제 요약
양의 정수 n이 주어지고, 이 숫자를 k진수로 바꿨을 때, 변환된 수 안에 아래 조건에 맞는 소수(Prime number)가 몇 개인지 구하는 문제
- 0P0처럼 소수 양쪽에 0이 있는 경우
- P0처럼 소수 오른쪽에만 0이 있고 왼쪽에는 아무것도 없는 경우
- 0P처럼 소수 왼쪽에만 0이 있고 오른쪽에는 아무것도 없는 경우
- P처럼 소수 양쪽에 아무것도 없는 경우
문제에서의 예시
예를 들어, 437674을 3진수로 바꾸면 211020101011입니다. 여기서 찾을 수 있는 조건에 맞는 소수는 왼쪽부터 순서대로 211, 2, 11이 있으며, 총 3개입니다. (211, 2, 11을 k진법으로 보았을 때가 아닌, 10진법으로 보았을 때 소수여야 한다는 점에 주의합니다.) 211은 P0 형태에서 찾을 수 있으며, 2는 0P0에서, 11은 0P에서 찾을 수 있습니다.
🟠 접근 방법
1 <= n <= 1,000,000 이므로, 1,000,000을 2진수로 바꿨을 때 길이가 M 이라면
1 <= M <= 20 -> 문자열 단계에서 필요한 시간 복잡도는 그리 크지 않은 것 같으니 그냥 일단 구현하면 되겠다.
n을 k진수로 바꾼 후 0을 기준으로 split
가장 왼쪽, 오른쪽 원소 -> P0, 0P 검사 : 그냥 가장 왼쪽, 오른속 원소가 소수인지
중간 원소 -> 0P0 검사 : 가운데 원소가 소수인지
원소가 하나일 경우 -> P 검사 -> 해당 원소가 소수인지
===> 결국 0을 split 한 리스트에서 소수 개수를 세면 된다.
🟡 해결 코드
from typing import List
def de2k(n:int, k: int) -> str: # 10진수(decimal) -> k진수
result = ''
while n > 0:
result += str(n%k)
n //= k
return str(result[::-1])
def isPrimeNumber(num: int) -> bool: # 소수 판별
if num == 1:
return False
elif num == 2:
return True
else:
for i in range(2, int(num**0.5)+1): # n의 n을 제외한 모든 약수는 [1, sqrt(n)] 내에 존재한다.
if num%i == 0:
return False
return True
def solution(n: int, k: int) -> int:
answer: int = 0
kNum: str = de2k(n, k) # k진수로 바꾸기
splitList: List[str] = kNum.split('0') # 0을 기준으로 split
for num in splitList: # 그 중 소수의 숫자 세기
if num and isPrimeNumber(int(num)):
answer += 1
return answer🙏 문제 접근 방법 및 코드에 대한 피드백과 질문은 환영입니다!
본 문제의 다른 풀이 및 피드백, 전체 문제 풀이 순서는 위 알고리즘 스터디 Repository에서도 확인 가능합니다.
Grow Exponentially