[프로그래머스] k진수에서 소수 개수 구하기 - Lv.2

프로그래머스 92335번 문제인 "k진수에서 소수 개수 구하기" Lv.2을 파이썬으로 풀어보도록 하겠습니다.

[프로그래머스] k진수에서 소수 개수 구하기 Lv.2 - [파이썬/python]

 

 

프로그래머스-k진수에서-소수-개수-구하기

---

💻 문제 설명

 

양의 정수 n이 주어집니다. 이 숫자를 k진수로 바꿨을 때, 변환된 수 안에 아래 조건에 맞는 소수(Prime number)가 몇 개인지 알아보려 합니다.

 

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

 

예를 들어, 437674을 3진수로 바꾸면 211020101011입니다. 여기서 찾을 수 있는 조건에 맞는 소수는 왼쪽부터 순서대로 211, 2, 11이 있으며, 총 3개입니다. (211, 2, 11을 k진법으로 보았을 때가 아닌, 10진법으로 보았을 때 소수여야 한다는 점에 주의합니다.) 211은 P0 형태에서 찾을 수 있으며, 2는 0P0에서, 11은 0P에서 찾을 수 있습니다.

 

정수 n과 k가 매개변수로 주어집니다. n을 k진수로 바꿨을 때, 변환된 수 안에서 찾을 수 있는 위 조건에 맞는 소수의 개수를 반환(return) 하도록 solution 함수를 완성해 주세요.

 

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

프로그래머스

---

🚨 제한사항

 

• 1 ≤ n ≤ 1,000,000
• 3 ≤ k ≤ 10

---

 

 

---

---

---

!!!정답 주의!!!

---

---

---

 

 

 

---

🌟 소스 코드

 

프로그래머스-k진수에서-소수-개수-구하기-파이썬-코드

 

 

 

def solution(n, k):

   

    count = 0 # 소수의 개수를 담을 변수

    converted = '' # n을 k진수로 변환할 문자열 변수

   

    # n을 k진수의 문자열로 변환

    while n > 0:

        n, mod = divmod(n, k)

        converted = str(mod) + converted

   

    # 0을 기준으로 문자열 분리하여 리스트로 변환

    converted = converted.split('0')

   

    # 각 부분 문자열이 소수인지 확인

    for num in converted:

        if num and is_prime(int(num)):

            count += 1

       

    return count

# 소수 판별 (제곱수 활용)

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

 

 

 

---

⏱ 시간복잡도

 

위 코드의 시간복잡는 O(n sqrt(m))입니다.

 

 

변수 할당: count = 0, converted = ''

변수 할당은 상수 시간, 즉 O(1)의 시간 복잡도를 가집니다.

 

반복문 순회 및 문자열 조작: while n > 0:

n을 k진수로 변환하는 데는 O(log n)의 시간이 소요됩니다. 이는 n을 k로 나누는 연산이 log n번 수행되기 때문입니다. 또한, 이 과정에서 문자열 조작이 이루어지지만, 이는 각 반복마다 상수 시간이 소요되므로 전체적인 시간 복잡도에는 영향을 미치지 않습니다.

 

문자열 분리: converted.split('0')

문자열 분리 연산은 O(n)의 시간 복잡도를 가집니다. 여기서 n은 문자열의 길이입니다.

 

반복문 순회 및 소수 판별: for num in converted:

모든 부분 문자열을 순회하며 소수 판별을 하는 데는 O(n sqrt(m))의 시간이 소요됩니다. 여기서 n은 부분 문자열의 개수, m은 각 부분 문자열의 정수 값입니다. 이는 각 부분 문자열에 대해 sqrt(m)까지의 수로 나누는 연산이 수행되기 때문입니다.

 

따라서, 이 코드의 전체 시간 복잡도는 O(1 + log n + n + n sqrt(m))입니다. 그러나 보통 복잡도에서는 가장 큰 항만을 고려하므로, 이 코드의 시간 복잡도는 O(n sqrt(m))으로 간주할 수 있습니다. 이는 입력 크기의 제곱근에 비례하는 시간 복잡도를 의미합니다.

---

🏳‍🌈 테스트 결과

 

프로그래머스-k진수에서-소수-개수-구하기-상태

 

 

프로그래머스-k진수에서-소수-개수-구하기-테스트-결과