알고리즘 | Algorithm

프로그래머스 | 2022 KAKAO BLIND RECRUITMENT > k진수에서 소수 개수 구하기 - 파이썬

개발자R 2022. 4. 13. 23:50
반응형

이번 문제도 간단한 문제였다.

그런데 왜이렇게 어렵게 풀었을까나 ㅜㅜ

 

주어진 숫자 n을 k진수로 바꾼 후, 0을 기준으로 숫자들을 잘라낸다.

그 숫자들이 소수인가?

그렇다면 소수인 숫자가 몇 개인가!

 

0을 기준으로 split하면 됐을텐데 나는 왜 for문을 돌면서 하나하나 체크했지ㅜㅜ?

 

def solution(n, k):
    answer = 0
    knum = transfer(n, k) + '0'
    curr = ''
    left = 0
    right = 0
    for digit in knum :
        if digit != '0':
            curr = curr + str(digit)
        else :
            if curr == '':
                continue
            if isPrime(int(curr)) and left == 0 and right == 0:
                answer = answer + 1
            left = right = 0
            curr = ''
    
    return answer

def isPrime(n):
    if n == 1 :
        return False
    for i in range(2, int(n**(1/2))+1) :
        if n % i == 0 :
            return False
    return True

def transfer(n, k):
    rest = n
    knum = ''
    if k == 10:
        return str(n)
    while rest != 0:
        knum = str(rest%k) + knum
        rest = rest//k
    return knum

 

소수 구하는 공식, k진수로 변환하는 것 정도는 외워야겠다.

다른 사람들 코드를 보고 다시 짜봤다.

def isPrime(n):
    i = 2
    if n == 1 :
        return False
    while i**2 <= n :
        if n % i == 0 :
            return False
        i += 1
    return True


def transfer(n, k):
    rest = n
    knum = ''
    if k == 10:
        return str(n)
    while rest != 0:
        knum += str(rest%k)
        rest = rest//k
    return knum[::-1]

사실 비슷하긴 함!

 

1. 소수 찾기 : while문에서 i를 n의 제곱근이랑 비교하는 방법도 있지만, i의 제곱을 n과 비교하는 방법도 있다.

2. k진수 변환하기 : 이것도 로직은 비슷하다. 그런데 나는 숫자를 추가할 때마다 앞쪽에 추가했는데, 그냥 뒤에 쭉 추가한 다음에 리턴할 때만 순서를 바꿔주는 것도 방법이다.

 

split을 사용한 솔루션 부분은 이렇게 바꾸면 된다.

def solution(n, k):
    answer = 0
    knum = transfer(n, k)
    for num in knum.split('0') :
        if num != '' and isPrime(int(num)) :
            answer += 1
    return answer

 

 

반응형