프로그래머스 k진수에서 소수 개수 구하기 (파이썬)

Level 2 Mathematics

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

코딩테스트 연습 - k진수에서 소수 개수 구하기

 

제출 코드

def checkPrime(num):
    if num <= 1:
        return False
    MAX = int(num**(0.5))
    for i in range(2, MAX + 1):
        if num % i == 0:
            return False
    return True

def convert(n, base):
    result = ''
    while n > 0:
        n, mod = n // base, n % base
        result += str(mod)
    # 역순인 진수를 뒤집어 줘야 원래 변환 하고자하는 base가 출력
    return result[::-1]


def solution(n, k):
    answer = 0
    string = convert(n, k)
    num = ""
    for i in range(len(string)):
        if string[i] != '0':
            num += string[i]
        else:
            if num:
                if checkPrime(int(num)):
                    answer += 1
                num = ""
    if num:
        if checkPrime(int(num)):
            answer += 1

    print(answer)
    return answer

10진수를 k진수로 변환하는 법을 몰라 검색하여 풀었습니다. 하지만 생각보다 간단하여 바로 이해할 수 있었습니다.

10진수를 8로 계속 나누어 몫이 0이 될 때 까지 반복하며 나머지를 리스트에 넣고 마지막에 뒤집어 반환하면 되는 것이었습니다.

 

110011에서 마지막 11을 계산하지 않고 for문을 탈출하여 마지막에 한번 더 num이 있다면 소수 체크를 했습니다. 

 

두번째 제출 코드

def checkPrime(num):
    if num <= 1:
        return False
    MAX = int(num**(0.5))
    for i in range(2, MAX + 1):
        if num % i == 0:
            return False
    return True

def convert(n, base):
    result = ''
    while n > 0:
        n, mod = n // base, n % base
        result += str(mod)
    # 역순인 진수를 뒤집어 줘야 원래 변환 하고자하는 base가 출력
    return result[::-1]

def solution(n, k):
    answer = 0
    string = convert(n, k)
    #print(bits)
    num = ""

    for num in string.split("0"):
        if not num: continue
        if checkPrime(int(num)):
            answer += 1
    
    return answer

다른 사람의 방법을 참고하여 0을 제거하는 방법을 인덱스로 하나하나 찾는 것이 아니라 split() 함수를 이용해서 0을 제거하며 숫자를 찾았습니다.

두번째 방법의 성능이 최대 4배 뛰어난 것을 확인할 수 있었습니다.