k진수에서 소수 개수 구하기 (92335번) - 프로그래머스 (Programmers)

https://school.programmers.co.kr/learn/courses/30/lessons/92335

프로그래머스

 

 

프로그래머스 - k진수에서 소수 개수 구하기 (92335번)

 

난이도 : Lv 2

알고리즘 : Mathematics (수학)

풀이 소요 시간 : 35 mins

 

 

def is_prime(x):
    if x == 2:
        return True
    if not x&1 or x == 1:
        return False
    for i in range(3, int(pow(x, 0.5))+1, 2):
        if not x%i:
            return False
    return True


def solution(n, k):
    kn = []
    while n:
        n, r = divmod(n, k)
        kn.append(r)
    cands = [int(i) for i in ''.join(map(str, kn[::-1])).split('0') if i]
    print(cands)
    if len(cands) == 1:
        return 1 if is_prime(cands[0]) else 0
    return sum(is_prime(cand) for cand in cands)

 

 

먼저 숫자 n을 k진수로 변환한다.

 

그리고 문자열로 변환한 뒤, '0'을 기준으로 split 을 적용한다.

 

---

 

만약 split 후 list의 길이가 1이라면, 그것은 0이 전혀 없는 숫자라는 뜻이다.

 

따라서, 해당 숫자가 소수이면

 

• P처럼 소수 양쪽에 아무것도 없는 경우

에 해당하므로, 정답으로 1을 출력한다.

 

소수가 아니라면 0을 정답으로 출력하면 된다.

 

---

 

만약 split 후 길이가 1보다 크다면, 그것은 중간에 0이 존재한다는 뜻이다.

 

split한 list의 각 숫자가 소수라면,

 

• 0P0처럼 소수 양쪽에 0이 있는 경우
• P0처럼 소수 오른쪽에만 0이 있고 왼쪽에는 아무것도 없는 경우
• 0P처럼 소수 왼쪽에만 0이 있고 오른쪽에는 아무것도 없는 경우

위의 3가지 중 하나에 반드시 해당한다.

 

따라서 split 한 list의 원소들 중, 소수의 개수를 세서 출력하면 된다.

 

 

---

 

소수 판별은, x의 제곱근까지 탐색하는 방식을 활용했다.