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

프로그래머스 2022 KAKAO BLIND RECRUITMENT

k진수에서 소수 개수 구하기

구현

 

---

※ 카카오 공식 해설

https://tech.kakao.com/2022/01/14/2022-kakao-recruitment-round-1/

2022 카카오 신입 공채 1차 온라인 코딩테스트 for Tech developers 문제해설

 

[문제]

10진수를 k진수로 변환하고 그 안에서 소수의 개수를 구하는 문제

제한사항에서 n의 수는 백만으로 넉넉한 편이다.

 

---

 

[과정]

 

우선 나의 경우에는 3가지의 단계로 순차적으로 나눴다.

• 10진수 -> k진수로 변환
• 변환된 수에서 0으로 나눠지는 수 찾기
• 해당 숫자의 소수 판별

---

1. 10진수 -> k진수로 변환

파이썬에서는 divmod라는 함수가 있어서 몫과 나머지를 한꺼번에 구할 수 있다.

divmod를 써서 나온 값을 역순으로 해주면 10진수를 k진수로 변환이 가능하다.

 

 

2. 변환된 수에서 0으로 나눠지는 수 찾기

조건을 봤을 때 모든 문항에서 공통적으로 보이는 부분이 0을 구분점으로 한다는 것이다.

따라서 숫자를 index 0번부터 n번까지 증가시키면서 0을 만나면 숫자를 저장한 임의의 배열(num)을 소수판별하면 된다.

이후 num은 다시 비워주는 방식.

 

 

3. 해당 숫자의 소수 판별

 

※ 시간초과 발생하는 경우

히든케이스 1번

# 소수 판별 알고리즘 -> (시간초과)
def is_prime_number(x):
    # 2부터 (x - 1)까지의 모든 수를 확인하며
    for i in range(2, x):
        # x가 해당 수로 나누어떨어진다면
        if x % i == 0:
            return False # 소수가 아님
    return True # 소수임

 

위처럼 만약 2부터 n-1번까지 반복할경우 시간초과가 발생한다.

(내가 했던 코드)

 

2부터 n // 2 까지 순회하며 검토하는 것은 짝지어 질 수 있는 약수까지 모두 검토하는 것이기 때문에 비효율적이다.

 

예시로, n = 21 일 때 3과 7은 짝지어져 3으로 나눴을 때 만으로 판별이 가능한데 7까지 순회하여 추가로 검토하게 된다.
따라서 소수를 판별할 때 2부터 n의 제곱근까지만 순회하여 검토해도 판별이 가능하다.

 

그래서 위처럼 해주어야 한다.

 

 

4. 마지막 추가 계산

그리고 반복후에 남은 num을 추가 계산해주어야 한다.

로직은 while문안의 코드와 동일하다.

 

---

 

[소스코드]

 

# 2022 KAKAO BLIND RECRUITMENT k진수에서 소수 개수 구하기

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

# 소수 판별
def is_prime_number(n):
    # 2부터 (x - 1)까지의 모든 수를 확인하며
    for i in range(2, int(n ** 0.5) + 1):
        if n % i == 0:
            return False
    return True

# 조선에 맞는 소수 찾기
def find_primeNum(data):
    cnt = 0   # 소수 개수
    num = ''  # 소수 판별할 수
    idx = 0   # 인덱스 번호
    
    while True:
        if idx == len(data):
            break
        # 오른쪽으로 idx를 이동하면서 0을 만날때마다 비교
        if data[idx] != '0':
            num += str(data[idx])
        else:
            if num != '':
                print(num)
                if num != '1' and is_prime_number(int(num)):    # 소수판별
                    cnt += 1
                num = ''                
        idx += 1
        
    # 마지막 계산
    if num != "":
        if num != '1' and is_prime_number(int(num)):    # 소수판별
            cnt += 1
    return cnt


def solution(n, k):
    answer = -1
    data = transformate_decimal(n,k)
    answer = find_primeNum(data)
    return answer

 

---

[통과]

 

---

 

5/12 스터디 과제 1