프로그래머스 / 구현, 정수론 / k진수에서 소수 개수 구하기

문제

---

 

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

프로그래머스

 

입출력

---

 

 

해설

---

 

n > 0에 상황에서 n을 k진수로 변환했을 때 조건에 맞는 소수가 몇 개인지 알아내는 문제이다.

 

다음과 같은 방법으로 풀이를 진행하였다.

 

1. n을 k진수로 변환한다.

2. k진수로 변환시 0을 기준으로 수들을 split한다.

3. split한 숫자들을 소수 판별한다.

4. 결과 도출

 

위와같은 생각을 한 이유는 주어진 조건을 보면서 설명하겠다.

 

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

조건을 잘 보면 모든 곳에서 0을 포함한 상태이다.

 

그렇기 때문에 0을 기준으로 숫자들을 split하게 된다면 모든 조건을 4번 조건으로 볼 수 있는 것이다.

추가적으로 소수 판별은 √n까지만 돌 수 있게 하여 빠르게 볼 수 있게끔 하였다.

 

그 이유는 n의 최대 수는 10^6이다.

고로 k진수로 변환 시 최대 10^12까지 나올 수 있다는 말이다.

진짜 우연의 일치로 10^12까지 0을 포함하지 않는 큰 수가 나오게 된다면 소수 판별시 시간 초과를 볼 수 있게 된다.

 

그렇기에 소수 판별을 √n까지 돌게 하는 테크닉을 사용하여 풀이를 진행하였다.

 

정답코드

---

'''
'25. 10. 11.(토)

1. 양의 정수 n이 주어짐
2. k진수로 바꾸었을 떄 조건에 맞는 소수가 몇 개인지 알아보려함.

1. k진수로 변환한다.
2. 해당 진수로 변환시 0으로 split한다.
3. 소수 판별한다(n^.5)
4. 결과 도출한다.
'''
def is_prime(n: int) -> bool:
    if n == 1:return False
    for i in range(2, int(n**.5) + 1):
        if n % i == 0:return False
    return True

def solution(n, k):
    answer = 0
    
    #현재 소수 담을 string
    number = ''
    
    #소수 판별
    while n:
        alpha = n % k#다음으로 넣을 숫자
        n//=k
        if alpha == 0:
            #현재까지 쌓은 number가 '' 가 아닌 있는 숫자이면서
            #소수인지 판별하여 갯수세주기
            if number and is_prime(int(number[::-1])):
                answer += 1
            number = ''
            continue
        #아니라면 number에 쌓기
        number += f'{alpha}'
    if number and is_prime(int(number[::-1])):
        answer += 1
    return answer

 

깃허브 : https://buly.kr/6MsOlV0

유튜브 : https://youtu.be/FQJ_1zZtrxU