[프로그래머스] [Level 2] [2022 KAKAO BLIND RECRUITMENT] k진수에서 소수 개수 구하기

문제) k진수에서 소수 개수 구하기

코딩테스트 연습 - k진수에서 소수 개수 구하기

 

• 내 풀이 1 (첫 시도 : fail)
  • for-else문 이용 
    • for문이 다 돌때까지 break가 되지 않으면 else문 실행
  • divod( a, b ) : 정수를 나눈 몫과 나머지를 동시에 구할 때 사용하는 함수
  • 10진수 → N진수 변환 

[Python] 2진수 / 8진수 / 16진수 / n진수 변환

def change(n, q): #N진수 변환하는 코드
    base = ''
    while n > 0:
        n, mod = divmod(n, q)
        base += str(mod)
    return base[::-1] 

def solution(n, k):
    number=change(n,k)
    result=''
    answer =0
    for n in number:
        if n=='0':
            if result== None: #null이면
                continue
            for i in range(2,int(result)//2+1):
                if int(result)%i==0:
                    result=''
                    break
            else: #for문이 끝날때까지 break 되지 않으면
                answer+=1
        else:
            result+=n
    if result: #0P 
        for i in range(2,int(result)//2+1):
            if int(result)%i==0:
                break
        else:
            answer+=1
        
    return answer

 

→ 실패 / 런타임 모두 존재

 

 

 

 

 

 

 

 

 

 

• 내 풀이 2
  • 약수 확인하는 과정의 범위: 2 ~ int(int(result)**0.5)+1 로 변경
  • k진수로 하나씩 변환하는 동시에 소수 판별 
    • deque을 이용해서 appendleft()로 변환값 역순 저장
  • result='1' 일 때를 고려해야 함

from collections import deque

def solution(n, k):
    answer =0
    result=''
    queue=deque()
    while n > 0:
        n, mod = divmod(n, k)
        result=''.join(queue)
        if mod==0:
            if not result or result=='1': #null이면
                queue.clear()
                continue
            for i in range(2,int(int(result)**0.5)+1):
                if int(result)%i==0:
                    queue.clear()
                    break
            else:
                answer+=1    
                queue.clear()
        else:
            queue.appendleft(str(mod))
            
    result=''.join(queue)
    if result: #P로 끝나는 경우
        for i in range(2,int(int(result)**0.5)+1):
            if int(result)%i==0:
                break
        else:
            answer+=1
            
    return answer

print(solution(437674,3))
print(solution(110011,10))
#결과
3
2

 

 

• 다른 사람 풀이
  • N진수 변환 함수 , 소수 판정 함수 따로 생성
  • s.split('0')으로 0기준으로 숫자 나눠서 소수 판별

# n을 k진법으로 나타낸 문자열 반환
def conv(n, k):
    s = ''
    while n>0:
        n, mod = divmod(n, k)
        s+=str(mod)
    return s[::-1]

# n이 소수인지 판정
def isprime(n):
    if n <= 1: return False
    for i in range(2,int(n**0.5+1)):
        if n%i == 0: return False
    return True

def solution(n, k):
    s = conv(n,k)
    cnt = 0
    for num in s.split('0'):
        if not num: continue # 빈 문자열에 대한 예외처리
        if isprime(int(num)): cnt += 1
    return cnt