문제
문제 설명
양의 정수 n이 주어집니다. 이 숫자를 k진수로 바꿨을 때, 변환된 수 안에 아래 조건에 맞는 소수(Prime number)가 몇 개인지 알아보려 합니다.
0P0처럼 소수 양쪽에 0이 있는 경우P0처럼 소수 오른쪽에만 0이 있고 왼쪽에는 아무것도 없는 경우0P처럼 소수 왼쪽에만 0이 있고 오른쪽에는 아무것도 없는 경우P처럼 소수 양쪽에 아무것도 없는 경우
단, P는 각 자릿수에 0을 포함하지 않는 소수입니다.
예를 들어, 101은 P가 될 수 없습니다.
예를 들어, 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
접근 방법
처음에는 조건이 4개밖에 없고, 0과 0 사이만 찾아서 구한 다음, 그 뒤에 소수임을 판별하면 되지 않나 싶어 투 포인터로 접근하려고 하였으나, 너무 과한 방법이었다.
left, right 두 포인터로 접근하더라도, 항상 왼쪽에 0이 존재한다는 보장 또는 오른쪽에 0이 존재한다는 보장이 없으므로 두 조건을 따로 처리해주어야 한다.
단, P는 각 자릿수에 0을 포함하지 않는 소수입니다.
이것이 주요 힌트이다.
우리가 주로 진법 변환을 할 때, 숫자 자료형을 문자형으로 바꾸게 된다. 따라서 먼저 진법 변환을 한 뒤, 문자열로 바꾼 결과를 .split("0")을 이용하여 0을 모두 제거하면, 위 4가지 조건을 모두 만족하는 P를 얻을 수 있다. 그 이후에는 소수만 걸러내면 원하는 결과를 얻을 수 있다.
코드
import math
from functools import reduce
def solution(n, k):
# filter(lambda x: x, ...)는 빈 문자열을 걸러내기 위한 함수다.
ret = list(map(int, filter(lambda x: x, transform(n, k).split("0"))))
answer = reduce(lambda acc, cur: acc + 1 if is_prime(cur) else acc + 0, ret, 0)
return answer
def is_prime(n):
# 빼먹지 말기, 1은 소수가 아니다.
if n == 1:
return False
for i in range(2, int(math.sqrt(n)) + 1):
if n % i == 0:
return False
return True
def transform(n, k):
string = ""
while n != 0:
remainder = n % k
share = n // k
string = str(remainder) + string
n = share
return string
