[Programmers] Lv2 - k진수에서 소수 구하기

문제

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

프로그래머스

 

풀이

문제의 조건은 아래와 같다.

• 0P0처럼 소수 양쪽에 0이 있는 경우
• P0처럼 소수 오른쪽에만 0이 있고 왼쪽에는 아무것도 없는 경우
• 0P처럼 소수 왼쪽에만 0이 있고 오른쪽에는 아무것도 없는 경우
• P처럼 소수 양쪽에 아무것도 없는 경우
• 단, P는 각 자릿수에 0을 포함하지 않는 소수입니다.
  • 예를 들어, 101은 P가 될 수 없습니다.

 

먼저 주어진 수 n을 k진법으로 변환한다.
그 후 조건에 만족하는 숫자들을 추려내서 소수인지 아닌지 판별한다.
즉 조건만족+소수 인 숫자들의 갯수를 return하는 문제.

 

아래는 첫번째 풀이다.

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

    number = ""
    while n:
        number = str(n % k) + number
        n //= k

    ret = 0
    curr = ""
    for num in number:
        if num != "0":
            curr += num
        else:
            if curr and is_prime(int(curr)):
                ret += 1
            curr = ""

    if curr and is_prime(int(curr)):
        ret += 1

    return ret

통과됐지만 너무 길었다.

 

while문을 통해 k진법으로 변환한 수 number을 구해주고,
for문으로 number을 하나씩 체크했다.
- 만약 0이 아니라면 curr에 더해준다.
- 0이라면 curr이 비어있는지 확인 후 is_prime()으로 curr이 소수인지 판별한다.
- 사용한 curr은 빈 문자열로 재할당한다.

마지막 남은 문자열도 남김없이 체크해준다.

 

너무 길어서 짜증났다. 아래는 두번째 코드.

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

    number = ""
    while n:
        number = str(n % k) + number
        n //= k

    numbers = number.split("0")
    return sum(is_prime(int(num)) for num in numbers if num)

아까보단 확실히 짧아졌다.

while문으로 number을 구하는 것까진 동일하다.

하지만 여기선 이 number을 "0"을 기준으로 분할해줬다.

분할해준 결과값 numbers를 순회하며 is_prime()으로 소수인지 판별해준다.
만약 True라면 1, False는 0을 반환하므로, sum()을 통해 모든 소수의 갯수를 구할 수 있다.