[프로그래머스] Python Level2 2022 KAKAO BLIND RECRUITMENT - k진수에서 소수 개수 구하기

문제 바로가기

접근 방법

• 소수 판별 함수 필요
• 진수 변환 함수 필요

1. 0으로 페이크를 주는 거 같은데 0P0, P0 이런거 사실 신경쓰지 않아도 된다.
2. n진수로 변환된 배열을 순회하며 소수가 몇개인지 찾으면 된다.
3. 투 포인터를 이용하여 순회한다.

코드

import math

def is_prime(n):
    if n == 1:
        return False
    for i in range(2, int(math.sqrt(n) + 1)):
        if n % i == 0:
            return False
    return True

def convert_to_binary(n, base):
    digits = []
    while n > 0:
        digits.insert(0, n % base)
        n //= base

    return digits

def solution(n, k):
    cnt = 0
    arr_binary = convert_to_binary(n, k)

    start, end = 0, 0
    while len(arr_binary) != end:
        strn = ''

		# 0 만나기 전까지 숫자 누적하기
        while arr_binary[end] != 0:
            strn += str(arr_binary[end])
            if end == len(arr_binary) - 1:
                break
            end += 1

        # 소수지만 0을 포함하면 안 됨.
        if strn != '' and is_prime(int(strn)) and '0' not in strn:
            cnt += 1
            start = end
            end = start + 1
        else:
            end += 1

    return cnt